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

## 開發紀錄

### q_size

須檢查 queue 為 `NULL` 的情形。

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

### q_new

建立空的 queue 時，必須把 head, tail 和 size 給定正確的初始值。

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_insert_head

如果 queue 是空的，表示 `q->head`, `q->tail`, `q->size` 都是初始值，此情況下若此函數被呼叫，`q->head` 和 `q->tail` 都應該指向新插入的 element。反之，`q->tail` 不須改變。

如果 `newh` 有被成功配置，但 `newh->value` 沒有，須將配置給 `newh` 的記憶體空間清空，避免 memory leak。

根據 C99 規格書 [7.24.6.3](http://port70.net/~nsz/c/c11/n1570.html#7.24.6.3)，`strlen()` 的回傳值為 terminating null character （即 `\0`）前的字元總數。為了將 `\0` 也複製到 `newh->value` 裡，配置給 `newh->value` 的大小和複製字串的長度都需要 +1。

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    int len = strlen(s);
    newh->value = (char *) malloc((len + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);

    newh->next = q->head;
    if (!q->head)
        q->tail = newh;
    q->head = newh;
    q->size += 1;
    return true;
}

### q_remove_head

`sp` 指向的大小有限制，如果 `q->value` 指向的大小超過該限制，須截斷並補上 `\0`。`sp` 的總長度是 `bufsize`，且題目要求字串必定要以 `\0` 結束，故求得 `q->value` 包含 `\0` 的字串長度 `len+1` 後，以 `maxlen` 存放 `bufsize` 和 `len+1` 的最小值。並且在複製字串後，強制補上 `\0`。

而若 `sp` 為 `NULL`，可直接忽略字串複製。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    list_ele_t *del = q->head;
    q->head = q->head->next;
    q->size -= 1;
    if (!q->head)
        q->tail = NULL;

    if (sp) {
        size_t len = strlen(del->value);
        size_t maxlen = len + 1 > bufsize ? bufsize : len + 1;
        strncpy(sp, del->value, maxlen - 1);
        sp[maxlen - 1] = '\0';
    }
    free(del->value);
    free(del);

    return true;
}

### q_free

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *del = q->head;
    while (del) {
        q->head = del->next;
        q->size -= 1;
        if (!q->head) {
            q->tail = NULL;
        }

        free(del->value);
        free(del);
        del = q->head;
    }
    free(q);
}

後參考 zxcvbnm04987 同學的[作業](https://hackmd.io/@mAleqROqS063_6sD0NUEYg/2020q1-lab0)，改為重用 `q_remove_head()` 的版本。

void q_free(queue_t *q)
{
    if (!q)
        return;

    while(q_remove_head(q, NULL, 0))
        ;

    free(q);
}

### q_insert_tail

與 `q_insert_head` 很相似，同樣需要處理 `queue` 是空的的情形。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh = (list_ele_t *) malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    int len = strlen(s);
    newh->value = (char *) malloc((len + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);
    newh->next = NULL;

    if (!q->head) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size += 1;
    return true;
}

### q_reverse

void q_reverse(queue_t *q)
{
    if (!q || !q->head)
        return;

    list_ele_t *current = q->tail;
    list_ele_t *prev;
    while (current != q->head) {
        prev = q->head;
        while (current != prev->next) {
            prev = prev->next;
        }
        current->next = prev;
        current = prev;
    }
    current->next = NULL;
    q->head = q->tail;
    q->tail = current;
}

原本這版從尾端做，太慢了，改為從頭做。

void q_reverse(queue_t *q)
{
    if (!q || !q->head || !q->head->next)
        return;

    list_ele_t *node = q->head->next;
    list_ele_t *prev = q->head;
    list_ele_t *next;
    while (node->next) {
        next = node->next;
        node->next = prev;
        prev = node;
        node = next;
    }

    q->tail = q->head;
    q->tail->next = NULL;
    q->head = node;
    q->head->next = prev;
}

### q_sort

~~暫時先用 bubble sort。~~

void q_sort(queue_t *q)
{
    if (!q || !q->head || q->size == 1)
        return;

    list_ele_t *current = q->head;
    list_ele_t *compare;
    char *tmp;

    while (current->next) {
        compare = current->next;
        while (compare) {
            if (current->value[0] > compare->value[0]) {
                tmp = current->value;
                current->value = compare->value;
                compare->value = tmp;
            }
            compare = compare->next;
        }
        current = current->next;
    }
}

改為 selection sort。原本的 bubble sort 交換次數太多，參考 [Linked list sort](https://npes87184.github.io/2015-09-12-linkedListSort/)，改用 selection sort 排序，在每個 sub-iteration 只把最小值存下來，iteration 結束前才做資料交換。

void q_sort(queue_t *q)
{
    if (!q || !q->head || q->size == 1)
        return;

    list_ele_t *current = q->head;
    list_ele_t *select;
    list_ele_t *min;
    char *tmp;

    while (current->next) {
        select = current->next;
        min = current;
        while (select) {
            if (strnatcasecmp(min->value, select->value) == 1) {
                min = select;
            }
            select = select->next;
        }
        tmp = min->value;
        min->value = current->value;
        current->value = tmp;
        current = current->next;
    }
}

參考自己寫的[第 1 週測驗題延伸問題](https://hackmd.io/@sharefun/H1SKqXrNI)，把 sorting 的演算法改為改良後的 merge sort。

:::warning
TODO:
換為 merge sort
:::

這邊是直接拿第一個字元比較，但其實 [C99 規格書](http://port70.net/~nsz/c/c11/n1570.html#7.24.4.2) 就有提到可以用 `strcmp()` 比較字串大小了。

作業提示須使用 natural sort，原因是 `strcmp()` 會判斷 `"a2" > "a10"`（以第一個相異的字元依 ASCII code 去比對大小）。要使上述判斷大小正確，可以限制字元數必須相等，如 `"a2"` 改為 `"a02"`，或是使用 natural sort。

1. 把 strnatcmp.[ch] 放到本專案下
2. 修改 Makefile

# Makefile
 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

3. queue.c 加入`#include "strnatcmp.h"` 並修改 `q_sort()`，使用 `strnatcmp()`
4. qtest.c 加入`#include "strnatcmp.h"` 並移除 `#include <string.h>`，在 `do_sort()` 把 `strcasecmp()` 改為 `strnatcmp()`

:::warning
TODO:
FIXME 尚未完成
:::

### Valgrind and Massif

初次實做完各主要功能後，開始嘗試使用 Valgrind 分析記憶體。

:::info
執行 `make valgrind` 時呼叫 subprocess 時會發生 `[Errno 2] No such file or directory` 錯誤，後已排除問題。

原問題如下：

$ make valgrind                                               
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/sharefun/Sources/sysprog2020/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  LD	qtest
make[1]: Leaving directory '/home/sharefun/Sources/sysprog2020/lab0-c'
cp qtest /tmp/qtest.GaS1n5
chmod u+x /tmp/qtest.GaS1n5
sed -i "s/alarm/isnan/g" /tmp/qtest.GaS1n5
scripts/driver.py -p /tmp/qtest.GaS1n5 --valgrind
-	Trace		Points
+ TESTING trace trace-01-ops:
Call of 'valgrind /tmp/qtest.GaS1n5 -v 1 -f ./traces/trace-01-ops.cmd' failed: [Errno 2] No such file or directory
-	trace-01-ops	0/6
+ TESTING trace trace-02-ops:
Call of 'valgrind /tmp/qtest.GaS1n5 -v 1 -f ./traces/trace-02-ops.cmd' failed: [Errno 2] No such file or directory
---	trace-02-ops	0/6
...

檢查 `/tmp` 下有該檔案，且直接執行 `valgrind /tmp/qtest.GaS1n5 -v 1 -f ./traces/trace-02-ops.cmd` 也可以成功。但是執行 `scripts/driver.py -p /tmp/qtest.vrlE1o --valgrind -t 02` 則否，與上面有相同的錯誤訊息。

我的環境是 Linux sharefun-X230 5.3.0-40-generic #32~18.04.1-Ubuntu SMP Mon Feb 3 14:05:59 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux，`/usr/bin/python` 版本是 2.7.17，shell 使用 zsh，改用 bash 也有一樣的問題。

最後是把 script/driver.py 呼叫外部程式的 `subprocess.call()` arguments 改成

// script/driver.py
- retcode = subprocess.call(clist)
+ retcode = subprocess.call(" ".join(clist), shell=True)

就可以正常執行了。

:::