---
# System prepended metadata

title: 2020q1 Homework1 (lab0)

---

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

## 實驗環境
```shell
$ uname -a
Linux 5.3.0-28-generic #30~18.04.1-Ubuntu SMP Fri Jan 17 06:14:09 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0
```

## 作業要求
- 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式
- 修改排序所用的比較函式，變更為 `natural sort`，在 “simulation” 也該做對應的修改，得以反映出 `natural sort` 的使用。
- 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;
- 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 :arrow_forward: 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

## 開發過程

### queue.h

```cpp
typedef struct {
    list_ele_t *head, *tail;
    int size;
} queue_t;
```

根據老師提供的作業說明所作的修改，加上一個 int size 變數在每次增減元素時做紀錄。

在實作```q_insert_tail```時，要求要將原本 $O(n)$ 的時間修改為 $O(1)$ ，因此在 ```queue_t``` 中增加一個 ```tail``` 指標，以便直接在 queue 的尾端新增元素。

參考 [OscarShiang ](https://hackmd.io/@WaryvM_MTuOkXtEEalFsvQ/Sy5oUP6MU#%E5%AF%A6%E4%BD%9C-q_reverse) 同學指標的使用方法，改用 `list_ele_t *tmp` 指標進行操作。

### queue.c

#### q_new

- 回傳一個空的 queue
- 當 malloc 失敗時需要回傳 NULL

```c
queue_t q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}
```

#### q_size

- return queue 的元素數量
- queue 為 NULL 時 return 0;

```c
int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

```
把 ```q->size``` 直接傳回去就是
一開始實作的時候沒考慮 queue 為 NULL 的情形，加進去之後分數會多六分


#### q_free

- 將 queue 中佔用的記憶體釋放
- 當 queue 為 NULL 時，直接 return 結束

```c
void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *tmp;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);  
}
```
從 head 依序拜訪各個元素並作釋放
最後再將 queue 的指標釋放

#### q_insert_head
- 從 queue 的 head 插入一個元素
- 當 queue 為 NULL 或分配位置時失敗 return false

```c
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
     newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char)*(strlen(s) + 1))
    if (!newh->value) {
        free(newh);
        return false;
    }
    snprintf(newh->value, strlen(s) + 1, "%s", s);
    newh->next = q->head;
    q->head = newh;
    if (!q->tail)
        q->tail = newh;
    q->size++;
    return true;
}
```
在 queue 為空時需要另外將 tail 也指向新增的元素

於作業說明中提到
>依據 [CERN Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml)
建議而移除 gets / sprintf / strcpy 等不安全的函式;

因此在將資料傳給 newh->value 時為了避免使用 strcpy ，改採用根據 CERN 所提供的建議中的snprintf函式來進行操作。

>**int snprintf(char * restrict s, size_t n, const char * restrict format, ...);**

在使用snprintf時，將參數 ```size_t n``` 設為 ```strlen(s)```時，會發現輸出結果跟預期的不一樣，如下
``` shell
cmd> new
q = []
cmd> ih 123
cmd> ih 123
q = [12]
```

在經查閱[C99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)之後，其對於 snprintf的敘述如下
> The snprintf function is equivalent to fprintf, except that the output is written into an array (specified by argument s) rather than to a stream. If n is zero, nothing is written, and s may be a null pointer. Otherwise, output characters beyond the n-1st are discarded rather than being written to the array, and a null character is written at the end of the characters actually written into the array. If copying takes place between objects that overlap, the behavior is undefined.

從中可以知道， ```snprintf``` 會根據 ```size_t n``` ，將第 n-1 個位置以後的字串捨棄，並在第 n 位放入 NULL，因此在利用 strlen(s) 作為 Buffer size 時，須加一才能將完整的 s 值傳進 ```newh->value``` 。

在 value 做 malloc 的時候，一開始是使用 ```sizeof(s)``` 配置記憶體空間，後來在後續的測試中發現傳入的字串大小大於等於 8 時，在進行釋放的時候會出現。
> ERROR: Corruption detected in block with address 0x558b91c49ce0 when attempting to free it

後來測試的時候發現 ```malloc(sizeof(s))``` 並不會配置一個跟 ```s``` 一樣的記憶體大小，而是 pointer 大小，導致在只用 ```sizeof(s)``` 作分配時不夠大，在用```snprintf``` 放入字串過大導致在釋放記憶體時動到了原本沒分配的部份，最後改用 ```sizeof(char)*strlen(s)+1``` 就可解掉這個 error，在 ```q_insert_tail``` 更新了一樣的作法。

根據 C 規格書中對 sizeof 的描述，如傳入的 sizeof(s) 中 s 是個陣列的話，是可以直接用的，當是 pointer 時就只會是 pointer 的大小，而在 64 位元的系統中，一個 pointer 的大小即是8個 byte 。
> When sizeof is applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1. 
When applied to an operand that has array type, the result is the total number of bytes in the array.
>103) When applied to an operand that has structure or union type, the result is the total number of bytes in such an object, including internal and trailing padding.


#### q_insert_tail
- 從 queue 的尾端新增一個元素
- 成功return true
- 若 queue 為 NULL 或分配位置失敗時則 return false
- 時間複雜度須為 $O(1)$ ，即不論 queue 的長度為何執行時間，操作步驟為固定數量。

```c
bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(sizeof(char)*(strlen(s) + 1))
        free(newh);
        return false;
    }
    snprintf(newh->value, strlen(s) + 1, "%s", s);
    newh->next = NULL;
    q->size++;
    if (!q->tail) {
        q->head = newh;
        q->tail = newh;
        return true;
    }
    q->tail->next = newh;
    q->tail = newh;
    return true;
}
```

在 queue 為空時需要另外將 head 也指向新增的元素

#### q_remove_head

- 將 queue head 刪除
- 成功刪除 return true
- 當 queue 為空或 NULL 時 return false
- 若 ```sp``` 不是 NULL 且 remove 執行成功時要將被 remove 的元素值的前bufsize - 1 位放進 ```sp``` 中，並且 sp 的最後一位須為 null terminator。
```cpp
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if(!q || !q->head)
        return false;
    list_ele_t *tmp;
    tmp = q->head;
    if (sp) {
        snprintf(sp, bufsize, "%s", tmp->value);
    }
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}
```

在將被 remove 值放進 sp 中，要求要取被 remove 的元素值前 bufsize - 1 位，在 insert 時用到的 ```snprintf```，剛好就可以拿來使用。

#### q_reverse
- 將 queue 的內容反轉
- queue 為 NULL 或 empty 時直接結束
- 不能 allocate 新的記憶體位址和 free 原有的記憶體位址

``` c
void q_reverse(queue_t *q)
{
    if (!q)
        return;
    if (q->size <= 1)
        return;
    list_ele_t *tmp;
    q->tail->next = q->head;
    while (q->head->next != q->tail) {
        tmp = q->head->next;
        q->head->next = tmp->next;
        tmp->next = q->tail->next;
        q->tail->next = tmp;
    }
    q->tail = q->head;
    q->head = q->head->next;
    q->tail->next = NULL;
}

```
除了 queue 為 NULL 和 empty 時，```q->size``` 為 1 時也可以直接結束。
一開始的想法是用拆一個接一個的方式從 ```q->head``` 依序將元素拆掉並重新反向接上，在接完之後需要另外將 ```q->tail``` 歸位。
後來想到先把 ```q->tail``` 接到 ```q->head``` 上，並依序將 ```q->head``` 到 ```q->tail``` 之間的元素接到 ```q->tail``` 後面，最後只須將```q-tail``` 和 ```q->head``` 互換位置，再將```q->tail->next``` 接到 NULL 即可，示意圖如下。

```graphviz
digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> a :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    tail [shape=box];
    tail -> c;
}
```

```graphviz
digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> b :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> a;
    tail [shape=box];
    tail -> c;
}
```
```graphviz
digraph linked_list{
    rankdir=LR;
    node [shape=record];
    a [label="{ <data> a | <ref>  }", width=1.2]
    b [label="{ <data> b | <ref>  }"];
    c [label="{ <data> c | <ref>  }"];
    a:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2];
    b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    c:ref:c -> b :data     [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false];
    head [shape=box];
    head -> c;
    tail [shape=box];
    tail -> a;
}
```

#### q_sort
- 將 queue 中元素小到大做排序
- 使用 natual sort (未完成)

``` cpp
void q_sort(queue_t *q)
{
    if (!q)
        return;
    if (q->size <= 1)
        return;
    merge_sort(&(q->head));
    while (q->tail->next)
        q->tail = q->tail->next;
}
```

##### sort.c
``` cpp
#include <stdio.h>
#include <string.h>

#include "queue.h"

void split(list_ele_t *source, list_ele_t **pre_head, list_ele_t **post_head)
{
    list_ele_t *fast, *slow;
    fast = source->next;
    slow = source;
    while (fast) {
        fast = fast->next;
        if (fast) {
            fast = fast->next;
            slow = slow->next;
        }
    }
    *pre_head = source;
    *post_head = slow->next;
    slow->next = NULL;
}

list_ele_t *merge(list_ele_t *pre_head, list_ele_t *post_head)
{
    list_ele_t *start, *current;
    start = pre_head;
    pre_head = pre_head->next;
    current = start;
    while (pre_head && post_head) {
        if (strcmp(pre_head->value, post_head->value) > 0) {
            current->next = post_head;
            post_head = post_head->next;
        } else {
            current->next = pre_head;
            pre_head = pre_head->next;
        }
        current = current->next;
    }
    if (pre_head)
        current->next = pre_head;
    else if (post_head)
        current->next = post_head;
    return start;
}

void merge_sort(list_ele_t **head)
{
    list_ele_t *pre_head, *post_head;
    if (!(*head))
        return;
    if (!(*head)->next)
        return;
    split(*head, &pre_head, &post_head);
    merge_sort(&pre_head);
    merge_sort(&post_head);
    if (strcmp(pre_head->value, post_head->value) <= 0) {
        *head = merge(pre_head, post_head);
    } else {
        *head = merge(post_head, pre_head);
    }
}
```

採用 merge sort 進行排序，即使在 worst case，merge sort 也是 $O(nlog{n})$ 的時間複雜度。實作的部份參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)

:::danger
TODO:
1. 在 `merge` 和 `merge_sort` 這二個函式都呼叫到 `strcmp`，也就是 comparator，倘若想更換後者為其他函式 (或傳遞函式指標)，那就需要在這兩個函式內容變更，不僅不便利，還會隱藏風險;
2. `split` 函式通用性不足，可改為巨集或 inline function 實作;
3. 考慮到 `merge_sort` 函式原型宣告的變更:
    ```cpp
    static list_ele_t *merge_sort(list_ele_t *head);
    ```
    輸入原本的 head，回傳因為排序而得到新的 head，在實作和使用上都會更便利;

:notes: jserv
:::

## 參考資料
* [2020 春季 lab0c 作業說明](https://hackmd.io/@sysprog/linux2020-lab0) 
* [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* [C11 規格書](https://web.cs.dal.ca/~vlado/pl/C_Standard_2011-n1570.pdf)
* [Drawing Graphs using Dot and Graphviz](http://www.tonyballantyne.com/graphs.html)