# 2020q3 Homework1 (lab0)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`

## 作業說明
利用 linked list 的各 function 實作，檢閱對 c 語言的認知，作業期望達到以下目標：
- 記憶體管理
- 建立並管理需要透過指標操作的資料結構
- 字串操作
- 改善特定關鍵操作的效能
- 提高程式碼的穩固程度，例如能夠處理無效的參數，包含 NULL 指標

## 環境

$ uname -a
Linux kuouu 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

## 實做`queue.c`
### q_new
新增一個新的 queue

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

必須注意 malloc 失敗時的處理方式

### q_free
將 queue 的記憶體釋放掉

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

    list_ele_t *curr = q->head;
    while (curr) {
        list_ele_t *next = curr->next;
        free(curr->value);
        free(curr);
        curr = next;
    }
    free(q);
}

除了 q ，還得釋放 q 中每個元素的記憶體

### q_insert_head
在 queue 的頭插入一個元素

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

    list_ele_t *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;
    }
    memset(newh->value, '\0', strlen(s) + 1);
    strncpy(newh->value, s, strlen(s));
    newh->next = q->head;
    q->head = newh;

    if (!q->tail)
        q->tail = newh;

    q->size++;
    return true;
}

得注意每次 malloc 時有沒有成功，以及複製字串時，須先將所需空間+1的位址全設為'\0'，最後再將新的元素加到 q 的頭。
若 q 的大小為0時，則須將該元素同時指定為 head 跟 tail

### q_insert_tail
在 queue 的結尾插入一個元素

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

    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (!newt)
        return false;
    newt->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newt->value) {
        free(newt);
        return false;
    }
    memset(newt->value, '\0', strlen(s) + 1);
    strncpy(newt->value, s, strlen(s));
    newt->next = NULL;

    if (q->head)
        q->tail->next = newt;
    else
        q->head = newt;
    q->tail = newt;
    q->size++;

    return true;
}

注意的地方同 q_insert_head。

### q_remove_head
移除 queue 開頭的元素

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

    list_ele_t *rm = q->head;
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, rm->value, bufsize - 1);
    }
    free(rm->value);
    q->head = q->head->next;
    free(rm);
    q->size--;
    if (q->size)
        q->tail = NULL;
    return true;
}

若是 q 不存在或大小為 1 ，則須回傳 false 。
在複製字串時一樣需要先全設為'\0'，並在釋放記憶體後將頭指到正確的位置。

### q_size
回傳 queue 的大小

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

若 q 不存在，則須回傳0

### q_reverse
反轉 queue

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

    list_ele_t *curr = q->head;
    list_ele_t *last = NULL;
    list_ele_t *next = NULL;
    q->tail = curr;
    while (curr) {
        next = curr->next;
        curr->next = last;
        last = curr;
        curr = next;
    }
    q->head = last;
}

從頭開始迭代，並從尾巴開始建立新的 queue

### q_sort
對 queue 作排序

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

    q->head = merge_sort(q->head);
    return;
}

list_ele_t *merge_sort(list_ele_t *head)
{
    // merge sort
    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;

    // sort each list
    list_ele_t *l1 = merge_sort(head);
    list_ele_t *l2 = merge_sort(fast);

    list_ele_t *merge = NULL;
    // merge sorted l1 and sorted l2
    while (l1 && l2) {
        if (strcasecmp(l1->value, l2->value) <= 0) {
            if (!merge) {
                head = merge = l1;
            } else {
                merge->next = l1;
                merge = merge->next;
            }
            l1 = l1->next;
        } else {
            if (!merge) {
                head = merge = l2;
            } else {
                merge->next = l2;
                merge = merge->next;
            }
            l2 = l2->next;
        }
    }

    if (l1)
        merge->next = l1;
    if (l2)
        merge->next = l2;
    return head;
}

與作業中 merge sort 的[連結](https://npes87184.github.io/2015-09-12-linkedListSort/)實作方法相同，差在比大小時須注意第一個 merge 的元素須特別處理。

## 運用 Valgrind 排除 qtest 實作的記憶體錯誤

$ valgrind -q --leak-check=full ./qtest -f traces/trace-13-complexity.cmd 
ERROR: Could not open source file 'traces/trace-13-complexity.cmd'
==4523== 32 bytes in 1 blocks are still reachable in loss record 1 of 24
==4523==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==4523==    by 0x10C636: malloc_or_fail (report.c:189)
==4523==    by 0x10D1B7: add_cmd (console.c:123)
==4523==    by 0x10D2A0: init_cmd (console.c:93)
==4523==    by 0x10BE31: main (qtest.c:759)
==4523==
.
.
.

使用 valgrind 發現從第13筆測資會出問題，但是目前還不知道如何解決