# 2021q1 Homework1 (lab0)
contributed by <`wiasliaw`>

###### tags: `sysprog2021`
[TOC]

## 進度
- [X] 依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 q_sort 函式
- [ ] 提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下
- [ ] 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- [ ] 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 在 qtest 中實作 coroutine，並提供新的命令 web，提供 web 伺服器功能，注意: web 伺服器運作過程中，qtest 仍可接受其他命令
- [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。
- [ ] 說明 antirez/linenoise 的運作原理，注意到 termios 的運用
- [ ] 研讀論文 Dude, is my code constant time?
- [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件 有關)，嘗試強化並提交 pull request

## 修改 queue.[ch] 和連帶的檔案

### queue.h

1. queue structure

- 為了達到要在 O(1) 的常數時間內執行完 `q_size` 和 `q_insert_tail`。在`queue_t` 新增兩個欄位 tail 和 size，前者紀錄 linked list 中最後一個 element 的 address，不需要訪整個 list 才知道最後一個 element。後者紀錄 list 中 element 的數量，不需要訪整個 list 才知道 element 的數量。

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

### queue.c

1. `q_new`

- 產生一個新的 queue。需要處理如果 `malloc` 請求記憶體失敗回傳的 NULL。

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

2. `q_free`

- 從 head 依序取出每個 element，先釋放掉 element 裡的字串，再釋放 element，最後再將 queue 釋放掉。

void q_free(queue_t *q)
{
    // if q is NULL, return false
    if (!q)
        return;
    while (q->head != NULL) {
        list_ele_t *temp = q->head;
        q->head = temp->next;
        free(temp->value);
        free(temp);
    }
    free(q);
}

3. `q_size`

- 在 queue_t 新增一個欄位 size，只要對 queue 中的 element 數量有影響的操作都有在 size 更新上正確的數量，查詢就能在 O(1) 內完成。另外還需要確認 q 是不是 NULL。

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

4. `q_insert_head` and `q_insert_tail`

- 建立一個新的 element，從 argument 複製字串的值到 element 中，並放到 queue 的 head/tail。
- 需要注意的是字串分配的空間大小，由於有字串結尾需要加上 `\0`，分配記憶體空間時需要額外多一，需要多，查到的 [stackoverflow](https://stackoverflow.com/questions/54079549/allocating-memory-for-a-string-in-c-using-malloc)
- return false 之前，先前成功宣告的記憶體有沒有被 free 處理掉。

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

    // create a element
    // return false if malloc fail
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    // create a string
    char *temp = malloc(sizeof(char) * (strlen(s) + 1));
    if (!temp) {
        free(newh);
        return false;
    }

    // copy string
    newh->value = temp;
    strncpy(newh->value, s, (strlen(s) + 1));

    // insert element to head
    newh->next = q->head;
    q->head = newh;
    // if there is no element in queue
    if (q->size == 0) {
        q->tail = newh;
    }
    q->size++;
    return true;
}

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

    // create a element
    // return false if malloc fail
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    // create a string
    char *temp = malloc(sizeof(char) * (strlen(s) + 1));
    if (!temp) {
        free(newh);
        return false;
    }

    // copy string
    newh->value = temp;
    strncpy(newh->value, s, (strlen(s) + 1));

    // insert element to head
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

5. `q_remove_head`

- 首先需要檢查 queue 是不是 NULL 或是 Empty
- 從 queue 中取出第一個 element，複製其 value 到 sp 後釋放掉

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    // if q is NULL or empty, return false
    if (!q || q->size == 0)
        return false;

    // remove an element from queue
    list_ele_t *target = q->head;
    q->head = q->head->next;

    // if sp is non-NULL, copy the string to *sp
    if (sp != NULL)
        strncpy(sp, target->value, bufsize);

    // free the element
    free(target->value);
    free(target);
    q->size--;
    return true;
}

6. `q_reverse`

- 從 head 開始，改變每個 element 的 next 位址

void q_reverse(queue_t *q)
{
    // if q is NULL or empty
    if (!q || q->size == 0)
        return;

    // assign tail to head
    q->tail = q->head;

    // change every element's next from head
    list_ele_t *rev_target = NULL, *current = q->head, *next;
    while (current) {
        next = current->next;
        current->next = rev_target;
        rev_target = current;
        current = next;
    }
    // assign head
    q->head = rev_target;
}

8. `q_sort`

- 實作 merge sort。拆成兩個 function，`list_merge_sort` 和 `list_merge`。前者主要將 list 切成更小的 list，並遞迴處理。後者主要將兩個 list 合併起來。

void q_sort(queue_t *q)
{
    // if q is NULL, empty or only one element
    if (!q || q->size <= 0)
        return;

    q->head = list_merge_sort(q->head);

    // redirect q->tail
    list_ele_t *temp = q->head;
    while (temp->next) {
        temp = temp->next;
    }
    q->tail = temp;

    return;
}

list_ele_t *list_merge_sort(list_ele_t *list)
{
    if (!list || !list->next)
        return list;

    // split
    list_ele_t *fast = list->next, *slow = list;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    list_ele_t *l1 = list_merge_sort(list);
    list_ele_t *l2 = list_merge_sort(fast);

    return list_merge(l1, l2);
}

list_ele_t *list_merge(list_ele_t *l1, list_ele_t *l2)
{
    // merge with recursive
    if (!l2)
        return l1;
    if (!l1)
        return l2;

    if (strcmp(l1->value, l2->value) < 0) {
        l1->next = list_merge(l1->next, l2);
        return l1;
    } else {
        l2->next = list_merge(l1, l2->next);
        return l2;
    }
}