# 2020q3 Homework1 (lab0)
contributed by < `p870613` >
###### tags: `sysprog2020`

## Outline
[TOC]

## 環境

uname -r                                
    5.4.0-37-generic

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\h]`實作
- main struct
- `q_new`: 建立新的空queue
- `q_free`: 釋放所有queue占有的記憶體
- `q_insert_head`: 在queue的head加入一個點
- `q_insert_tail`: 在queue的tail加入一個點
- `q_remove_head`: 在queue的head移除一個點
- `q_size`： 計算queue的元素數量
- `q_reserve`: 以反向順序重新排列queue
- `q_sort`: 以遞增順序來排序queue
## lab0 實作
- main struct
- 在struct的部分, 主要的變動是在`queue_t`中新增成員 `tail`, `size`, 新增`tail`與`size`的主要原因是在`q_size`與`q_insert_tail`時間複雜度需要`O(1)`。

typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

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

- q_new
- `q_new`實作時有考慮`malloc`失敗的情況

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

- q_free
- 用`del_node`作為釋放用節點,把`del_node`作為參數傳進`free_node`之後檢查節點與節點所指向的value是否為NULL,避免free到NULL節點
- 用`*cur`作為移動用節點

void free_node(list_ele_t *node)
{
    if (node != NULL) {
        if (node->value != NULL) {
            free(node->value);
        }
        free(node);
    }
    return;
}

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    if (q->head == NULL) {
        free(q);
        return;
    }

    list_ele_t **cur = &(q->head);
    while (*cur) {
        list_ele_t *del_node = *cur;
        *cur = ((*cur)->next);
        free_node(del_node);
    }
    free(q);
}

- q_insert_head
- 將new node放入queue的前端
- 先檢查`q`與`s`是否為NULL
- 利用`q_is_null`查看`q->head`是否為NULL, 如果為NULL就代表`q->head`與`q->tail`指向相同點, 用`q_null_queue_add_node`去設定
- 之後把new node的next設為`q->head`, `q->head`設為new node

bool q_is_null(queue_t *q)
{
    if (q->head == NULL)
        return true;
    return false;
}
void q_null_queue_add_node(queue_t *q, list_ele_t *node)
{
    if (node != NULL) {
        q->tail = node;
        node->next = NULL;
    }
}

bool q_insert_head(queue_t *q, char *s)
{
    if (s == NULL || q == NULL)
        return false;

    list_ele_t *newh = node_init(s);
    if (newh == NULL)
        return false;

    if (q_is_null(q))
        q_null_queue_add_node(q, newh);
    newh->next = q->head;
    q->head = newh;
    q->size++;

    return true;
}

- q_insert_tail
- 將新的node放入queue的尾端
- 先檢查`q`與`q->head`的狀態, 如果`q->head`是NULL的話，`q->head`與`q->tail`指向相同的點

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL || s == NULL)
        return false;

    list_ele_t *new_node = node_init(s);

    if (new_node == NULL)
        return false;
    if (q->head == NULL)
        q->head = new_node;
    else if (q->tail != NULL)
        q->tail->next = new_node;

    new_node->next = NULL;
    q->tail = new_node;
    q->size++;
    return true;
}

- q_remove_head
- 先確認`q` 與 `q->head`的狀態, 如果為NULL, return false
- 用`del_node`作為釋放資源的點

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q != NULL && q->head != NULL) {
        list_ele_t *del_node = q->head;
        q->head = q->head->next;

        if (sp != NULL) {
            strncpy(sp, del_node->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
            printf("%s\n", sp);
        }

        free_node(del_node);

        q->size--;
        if (q->size == 0) {
            q->tail = NULL;
            q->head = NULL;
        }
        return true;
    } else
        return false;
}

- q_size
- 回傳`q->size`

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

- q_reverse
- 只用`cur`, `pre`, `next` 實現反轉queue
- 藉由`pre`指向`cur`的前一個點, `next`指向`cur`的下一個點, 藉由`cur->next = pre`改變queue的方向
- 最後記得`q->tail`與`q->head`需要互換

void q_reverse(queue_t *q)
{
    if (q == NULL)
        return;
    if (q->head == NULL || q->size == 0 || q->size == 1)
        return;


    list_ele_t *cur = q->head;
    list_ele_t *pre = NULL, *next;
    while (cur) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    list_ele_t *tmp = q->head;
    q->head = q->tail;
    q->tail = tmp;
}

- q_sort
- 使用`find_mid_node`找尋中間的node, 方法為： 使用兩變數`slow` 與 `fast` ， 讓`fast`traverse的node 為`slow`的 2 倍, 所以當`fast`到最後的node, `slow`就在中間
- `merge_sort`的原理是先找到list的中間node，並斷鏈,從code的角度出發, `*mid = find_mid_node(*head);`就是找尋中間的node, 之後分成`right`與`left`分成list的左半部與右半部，然後要記得斷開鏈結`mid->next = NULL;`, 之後進入recursive直到list的node只剩一個node
- 分完之後,要回來結合了，首先先使用`**tmp = &head`, 存取`head`的值與`*head`所指向的值,之後使用`strcmp(left->value, right->value) < 0`判斷哪邊比較大,如果是`left`比較大, 使用`*tmp = left; left = left ->next`, 反之`right`亦然; 最後用`tmp = &((*tmp)->next);`串起連結
- 最後記得要把`q->tail`換成sort完的tail

list_ele_t *find_mid_node(list_ele_t *head)
{
    list_ele_t **fast = &(head->next);
    list_ele_t **slow = &head;

    while (*fast != NULL && (*fast)->next != NULL) {
        slow = &((*slow)->next);
        fast = &((*fast)->next->next);
    }
    return *slow;
}

void merge_sort(list_ele_t **head)
{
    if (!(*head) || !((*head)->next))
        return;

    list_ele_t *mid = find_mid_node(*head);

    list_ele_t *right = mid->next;
    mid->next = NULL;
    list_ele_t *left = *head;

    merge_sort(&left);
    merge_sort(&right);

    *head = NULL;
    list_ele_t **tmp = head;

    while (left && right) {
        if (strcmp(left->value, right->value) < 0) {
            *tmp = left;
            left = left->next;
        } else {
            *tmp = right;
            right = right->next;
        }
        tmp = &((*tmp)->next);
    }

    if (left != NULL)
        *tmp = left;
    else
        *tmp = right;
}
void q_sort(queue_t *q)
{
    if (q == NULL)
        return;
    if (q->size == 0 || q->size == 1 || q->head == NULL)
        return;

    merge_sort(&(q->head));

    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}