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

### 作業要求

#### fork [lab0-c](https://github.com/sysprog21/lab0-c), 依據指示著手修改 queue.[ch] 和連帶的檔案

- [ ] 詳細閱讀 C Programming Lab
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_size
- [x] q_reverse
- [x] q_sort

### 開發紀錄

#### q_new

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

使用 sizeof 取得 queue_t 結構所需的記憶體大小, malloc 可以配置記憶體並取得該記憶體位置, 透過指標設定初始值, tail 與 size 可使部份函式的時間複雜度縮減到 O(1)

#### q_free

{
    if (q == NULL) {
        return;
    }

    list_ele_t *nextt = q->head;

    while (nextt) {
        free(nextt->value);
        list_ele_t *tmp = nextt->next;
        free(nextt);
        nextt = tmp;
    }

    free(q);
}

從 head 開始往後找, 找到一個節點後, 暫存指向下一個節點的指標, 釋放該節點所使用的字串空間和本身的空間

#### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *copied_string;

    if (q == NULL) {
        return false;
    }

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

    copied_string = malloc(strlen(s) + 1);
    if (copied_string == NULL) {
        free(newh);
        return false;
    }

    strlcpy(copied_string, s, (strlen(s) + 1) * sizeof(char));

    newh->next = q->head;
    newh->value = copied_string;
    q->head = newh;
    if (q->tail == NULL) {
        q->tail = newh;
    }
    q->size++;

    return true;
}

先配置好新節點所需的空間與其使用的字串空間, 將 head 改為指向新節點, 如果 tail 不存在, 表示新節點也是最後一個節點, 也要將 tail 改為指向新節點, 並且調整 size

這段程式配置兩次記憶體, 如果第二次失敗, 記得要釋放掉第一次的空間

執行 `git commit -a` 會出現以下錯誤

Dangerous function detected in /home/user/linux2021/lab0-c/queue.c
strcpy ...

參考 [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 用 strlcpy 替換調 strcpy

#ifndef strlcpy
#define strlcpy(dst, src, sz) snprintf((dst), (sz), "%s", (src))
#endif

#### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;
    char *copied_string;

    if (q == NULL) {
        return false;
    }

    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }

    copied_string = malloc(strlen(s) + 1);
    if (copied_string == NULL) {
        free(newt);
        return false;
    }
    strlcpy(copied_string, s, (strlen(s) + 1) * sizeof(char));

    newt->next = NULL;
    newt->value = copied_string;
    if (q->tail) {
        q->tail->next = newt;
    }
    q->tail = newt;
    if (q->head == NULL) {
        q->head = newt;
    }
    q->size++;

    return true;
}

跟 q_insert_head 的概念類似, head 為 `NULL` 指標時插入新節點, 表示該節點也是第一個節點, 因此需要修改 head

#### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    list_ele_t *nextt = NULL;

    if (q == NULL || q->head == NULL) {
        return false;
    }

    char *string = q->head->value;

    if (sp != NULL) {
        int i;
        for (i = 0; i < bufsize - 1; i++) {
            *(sp + i) = *string;
            string++;
        }
        *(sp + i) = '\0';
    }

    free(q->head->value);
    nextt = q->head->next;
    free(q->head);
    q->head = nextt;
    if (q->head == NULL) {
        q->tail = NULL;
    }

    q->size--;

    return true;
}

#### q_size

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

#### q_reverse

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

    int i;
    list_ele_t *prevt = NULL;
    list_ele_t *thist = q->head;

    for (i = 0; i < q->size; i++) {
        if (i == 0) {
            q->tail = thist;
        } else if (i == q->size - 1) {
            q->head = thist;
        }

        list_ele_t *tmp = thist->next;
        thist->next = prevt;
        prevt = thist;
        thist = tmp;
    }
}

### q_sort

void q_bubble_sort(queue_t *q)
{
    for (int i = q->size; i > 0; i--) {
        list_ele_t *thist = q->head;

        for (int j = 0; j < i - 1; j++) {
            if (strcmp(thist->value, thist->next->value) > 0) {
                char *tmp = thist->value;
                thist->value = thist->next->value;
                thist->next->value = tmp;
            }
            thist = thist->next;
        }
    }
}

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

    q_bubble_sort(q);
}

執行 make test

+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
---     trace-15-perf   0/6
+++ TESTING trace trace-16-perf:

執行 ./qtest 執行 sort 沒有發現無窮迴圈, 目前判斷是使用 bubble sort 效率太差

~~因為太不了解指標, 嘗試要寫 merge sort 還沒有成功~~

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

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

    // 從 tail 指向的節點開始找,每當有下一個就改成是新的最後一個,直到找不到
    // 這個寫法效率不佳,應該要在 merge_sort 裡面改好 q->head, q->tail
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

list_ele_t *merge_sort(list_ele_t *node)
{
    // 當 queue 有兩個元素時才有 sort 的必要
    if (!node || !node->next) {
        return node;
    }

    // 讓 fast 端移動的速度快一個節點,直到到達尾端
    // 以下程式碼可以把一段元素分成兩段
    
    list_ele_t *slow = node;
    list_ele_t *fast = node->next;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;

    // 分成兩段後,使用遞迴分成兩段,直到每段剩下一個元素

    list_ele_t *node1 = merge_sort(node);
    list_ele_t *node2 = merge_sort(fast);

    // 把各個段再合併起來
    // 因為是遞迴到每段剩下一個元素再合併回去
    // 合併時等於是合併已排序過的兩段
    
    return merge(node1, node2);
}

之前不太了解有些演算法題目會改一個前提: 已知有兩個排序過的陣列,請你合併並且排序

這次寫了這個題目後了解到在 Divide-and-conquer algorithm 中,因為問題會被切成更小的子問題,子問題解了之後就會得到類似已排序過的結果

list_ele_t *merge(list_ele_t *head1, list_ele_t *head2)
{
    // 因為是要遞增,所以要知道比較小的一段當作頭,並且在最後回傳
    list_ele_t *head = strcmp(head1->value, head2->value) <= 0 ? head1 : head2;
    
    // 紀錄上一個較小值
    list_ele_t *cursor = NULL;

    while (head1 && head2) {
        // 將兩段的元素做比較
        // cursor 指向較小的元素
        // 如果 cursor 已經有前一個較小的元素,設定 next 讓他們串起來
        // 比較小的元素所在的那一段的指標要往下一個移動
    
        if (strcmp(head1->value, head2->value) <= 0) {  // 1 <= 2    
            if (!cursor) {
                cursor = head1;
            } else {
                cursor->next = head1;
                cursor = cursor->next;
            }
            head1 = head1->next;
        } else {
            if (!cursor) {
                cursor = head2;
            } else {
                cursor->next = head2;
                cursor = cursor->next;
            }
            head2 = head2->next;
        }
    }
    
    // 比較完之後,檢查沒有被比較完的
    if (head1) {
        cursor->next = head1;
    } else if (head2) {
        cursor->next = head2;
    }

    return head;
}