# 2020q3 Homework1 (lab0)
contributed by < [@wiasliaw77210](https://github.com/wiasliaw77210) >

###### tags: `sysprog2020`

## Outline

[TOC]

## Environment

### Kernel

uname -srv
# Linux 4.15.0-115-generic #116-Ubuntu SMP Wed Aug 26 14:04:49 UTC 2020

### Compiler

gcc -v
# gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04) 

## Requirement

### queue implement

<pre>
queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:

q_new: 建立新的「空」佇列;
q_free: 釋放佇列所佔用的記憶體;
q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
q_size: 計算佇列中的元素數量。
q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
q_sort: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;
</pre>

#### data type

/* queue.h */

/* Queue structure */
typedef struct {
    list_ele_t *head, *last;
    int size;
} queue_t;

#### q_new

> Requirement
> 1. Create empty queue.
> 2. Return NULL if could not allocate space.

根據 [參考](https://en.cppreference.com/w/c/memory/malloc), `malloc` 如果沒有辦法分配記憶體給 `q` 或是出現錯誤，會回傳 `NULL`。所以透過檢查 `q` 是否是 NULL 即可。

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

#### q_free

> Requirement
> 1. Free all the element in queue
> 2. Free queue structure

從 queue 的 head 開始，將每個 head 之中的 char* 指標與 head 都釋放掉，最後再來釋放 queue。

void q_free(queue_t *q)
{
    if (!q)
        return;
    while (q->head) {
        list_ele_t *node = q->head;
        q->head = q->head->next;
        free(node->value);
        free(node);
    }
    free(q);
}

#### q_insert_head

> Requirement
> 1. Return true if successful.
> 2. Return false if q is NULL or could not allocate space.
> 3. allocate space for the string and copy it

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));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s));

    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->last = newh;
    q->size++;
    return true;
}

#### q_insert_tail

bool q_insert_tail(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));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, strlen(s));

    newh->next = NULL;
    if (q->last != NULL)
        q->last->next = newh;
    else
        q->head = newh;
    q->last = newh;
    q->size++;
    return true;
}

#### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /*
     * Check if queue is NULL or EMPTY
     */
    if (!q || !q->head)
        return false;

    list_ele_t *node = q->head;

    // if sp is non-NULL, copy the removed element's value
    if (sp) {
        memset(sp, 0, bufsize);
        strncpy(sp, node->value, bufsize);
    }
    // remove and free the element
    q->head = q->head->next;
    q->size--;
    free(node->value);
    free(node);
    return true;
}

#### q_size

> Requirement
> 1. Return number of elements in queue.
> 2. It should operate in O(1) time.

我在 `queue_t` 新加了一個欄位 `size`，用以紀錄 queue 之中的數量，所以在其他 `queue` method 都有正確的實作之下，將 `size` 回傳即可。

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

#### q_reverse

void q_reverse(queue_t *q)
{
    list_ele_t *current = q->head, *prev = NULL, *next = q->head->next;
    q->last = q->head;
    while (next != NULL) {
        current->next = prev;
        prev = current;
        current = next;
        next = next->next;
    }
    current->next = prev;
    q->head = current;
}

#### q_sort

list_ele_t *mergeSort(list_ele_t *head)
{
    // check condition
    if (!head || !head->next)
        return head;

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

    list_ele_t *l1 = mergeSort(head);
    list_ele_t *l2 = mergeSort(fast);
    return sortedMerge(l1, l2);
}

list_ele_t *sortedMerge(list_ele_t *a, list_ele_t *b)
{
    // check condition
    if (!a)
        return b;
    else if (!b)
        return a;

    if (strcmp(a->value, b->value) < 0) {
        a->next = sortedMerge(a->next, b);
        return a;
    } else {
        b->next = sortedMerge(a, b->next);
        return a;
    }
}

## 遇到的問題

1. Merge Sort Segmentation fault occurred

不知道哪個 statement 造成

## 參考資料

- [lab0 說明](https://hackmd.io/@sysprog/2020-lab0#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)
- [Merge Sort](https://github.com/alrightchiu/SecondRound/blob/master/content/Algorithms%20and%20Data%20Structures/BasicDataStructures/LinkedList/Article/LinkedList_MemberFunction.md)
- [Merge Sort - geeksforgeeks](https://www.geeksforgeeks.org/merge-sort-for-linked-list/)