# 2025q1 Homework1 (lab0)
contributed by <[`kk908676`](https://github.com/kk908676)>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## Reviewed by BennyWang1007
1. 倉庫並未包含指定 commit `4a2ff9f`。
2. 此份筆記不是讓你展示所有程式碼的地方，只展示部分即可。
3. Commit message 應再更詳細，包含如何實作等訊息，如 commit `3332488`、`b9c75d6`、`bc4a8de`、`690a6d1`、`72bc268`。
4. Merge sort 的時間複雜度應為 $O(n\ log(n))$。
5. 此筆記僅包含 `queue.c` 實作，其餘部分有時間可以慢慢補上。

## 開發環境

$ hostnamectl 
Operating System: Ubuntu 24.04.1 LTS              
Kernel: Linux 5.15.167.4-microsoft-standard-WSL2

$ gcc --version                                         
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:           x86_64
CPU op-mode(s):         32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                 16
On-line CPU(s) list:    0-15
Vendor ID:              GenuineIntel
Model name:             Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU family:             6
Model:                  165
Thread(s) per core:     2
Core(s) per socket:     8
Socket(s):              1
Stepping:               5
CPU(s) scaling MHz:     29%
BogoMIPS:               5808.02    
L1d:                    256 KiB (8 instances)
L1i:                    256 KiB (8 instances)
L2:                     2 MiB (8 instances)
L3:                     16 MiB (1 instance) 

## 佇列實作與改進

### `q_new`
宣告一個結構指標queue，透過 `malloc` 配置記憶體，並使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的`INIT_LIST_HEAD` 進行初始化，讓 next 和 prev 都指向 queue 本身。需要注意的是，當記憶體配置失敗時，返回 return

struct list_head *q_new()
{
    struct list_head *queue = malloc(sizeof(struct list_head));

    if (!queue) {
        return NULL;
    }

    INIT_LIST_HEAD(queue);

    return queue;
}

### `q_free`
使用 `While` 走訪每個節點。在走訪的過程中，將節點逐個刪除

void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *cur = head->next;

    while (cur != head) {
        struct list_head *temp = cur;
        cur = cur->next;

        element_t *item = container_of(temp, element_t, list);
        free(item->value);
        free(item);
    }

    free(head);
}

### `q_insert_head`
原始版本 :
* 使用 strdup() 可以動態配置字串的記憶體空間，沒有使用 strncpy() 的原因是需要另外計算字串長度
* 判斷 `head` 是否為空佇列，是的話直接新增為下一個節點，否則宣告一個結構指標 `old` 記錄下一個節點再進行新增

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *item = (element_t *) malloc(sizeof(element_t));
    if (!item) {
        return false;
    }
    item->value = strdup(s);

    if (head->next == head) {
        head->next = &item->list;
        head->prev = &item->list;
        item->list.next = head;
        item->list.prev = head;
    } else {
        struct list_head *old = head->next;
        head->next = &item->list;
        old->prev = &item->list;
        item->list.next = old;
        item->list.prev = head;
    }

    return true;
}

改進版本 :
* 不必考慮 `head` 是否為空佇列，因為我們只需要宣告一個指標指向 `head` 的下一個進行插入
* 把原本的程式瑪使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_add()` 函式代替，將新增的節點添加在佇列的開頭

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = malloc(sizeof(element_t));
    if (!item)
        return false;

    item->value = strdup(s);
    if (!item->value) {
        free(item);
        return false;
    }

    list_add(&item->list, head);
    return true;
}

### `q_insert_tail`
作法與 `q_insert_head()` 差異在於節點插入的位置不同，使用 `list_add_tail()` 函式將節點新增在尾端

-   list_add(&item->list, head);
+   list_add_tail(&item->list, head);

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *item = malloc(sizeof(element_t));
    if (!item) {
        return false;
    }

    item->value = strdup(s);
    if (!item->value) {
        free(item);
        return false;
    }

    list_add_tail(&item->list, head);
    return true;
}

### `q_remove_head`
* 在佇列不為空的情況下，宣告一個結構指標 `remove` 指向 `head->next`
* 使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_del()` 將節點從 linked list 上 **remove**，成為單獨的節點

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *remove = head->next;
    element_t *re_item = container_of(remove, element_t, list);

    list_del(remove);

    if (sp != NULL) {
        strncpy(sp, re_item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return re_item;
}

### `q_remove_tail`
作法與 `q_remove_head()` 差不多相同，差異在於移除節點的位置不同，結構指標 `remove` 指向的是 `head->prev`

-   struct list_head *remove = head->next;
+   struct list_head *remove = head->prev;

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *remove = head->prev;
    element_t *re_item = container_of(remove, element_t, list);

    list_del(remove);

    if (sp != NULL) {
        strncpy(sp, re_item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return re_item;
}

### `q_size`
使用 `while` 走訪每個節點並計算其節點數量

int q_size(struct list_head *head)
{
    if (!head || head->next == head)
        return 0;

    int count = 0;
    struct list_head *temp = head->next;
    while (temp != head) {
        count++;
        temp = temp->next;
    }

    return count;
}

### `q_delete_mid`
使用 `q_size()` 計算節點數量，算出 `⌊n / 2⌋` 即為我們想要刪除的節點

bool q_delete_mid(struct list_head *head)
{
    struct list_head *temp = head;

    int count = q_size(head);
    if (!head)
        return false;
    if (list_empty(head))
        return true;

    count = count / 2 + 1;
    while (count != 1) {
        temp = temp->next;
        count -= 1;
    }
    element_t *re_item = container_of(temp->next, element_t, list);

    temp->next->next->prev = temp;
    temp->next = temp->next->next;

    free(re_item->value);
    free(re_item);

    return true;
}

### `q_delete_dup`
函式假設： `*head` 是排序好的鏈結串列
在 `While` 中我們會透過 `cur` 來指向當前的節點並走訪完整個鏈結串列，接著跟下一個節點也就是 `temp` 來檢查是否有節點重複的情況，如果發生了會先刪除 `temp` 指向的節點，當重複的節點都刪除完後有 `bool dup` 來紀錄當前的節點是否也要進行刪除

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *cur = head->next;

    while (cur != head) {
        element_t *node1 = container_of(cur, element_t, list);
        struct list_head *temp = cur->next;
        bool dup = false;

        while (temp != head) {
            element_t *node2 = container_of(temp, element_t, list);

            if (strcmp(node1->value, node2->value) == 0) {
                dup = true;
                temp = temp->next;
                list_del(&node2->list);
                free(node2->value);
                free(node2);
            } else {
                break;
            }
        }

        struct list_head *next = cur->next;
        if (dup) {
            list_del(cur);
            free(node1->value);
            free(node1);
        }
        cur = next;
    }
    return true;
}

### `q_swap`
當目前節點大於一個時，宣告兩個結構指標 `node1` 、 `node2` 進行兩兩的交換

void q_swap(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    while (count > 1) {
        struct list_head *temp = head;

        element_t *node1 = container_of(temp->next, element_t, list);
        element_t *node2 = container_of(temp->next->next, element_t, list);

        temp = head->next->next->next;

        head->next = &node2->list;
        temp->prev = &node1->list;

        node2->list.next = &node1->list;
        node2->list.prev = head;
        node1->list.next = temp;
        node1->list.prev = &node2->list;

        count -= 2;
        head = head->next->next;
    }
}

### `q_reverse`
使用 `cur` 走訪原始的鏈結串列，再使用 `cur` 、 `temp` 紀錄當前節點以及下一個節點並交換彼此的指標來反轉鏈結串列

void q_reverse(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    struct list_head *cur = head;
    struct list_head *temp = head->next;

    do {
        cur->next = cur->prev;
        cur->prev = temp;
        temp = temp->next;
        cur = cur->prev;
    } while (cur != head);
}

### `q_reverseK`
`temp` : 指向未完成反轉的串列
`count` ： 紀錄訪問節點個數
每當訪問 K 個節點， 就將那 K 個節點透過 `list_cut_position(&head_to, temp, node)` 切出來放到 `head_to` ，並透過 `q_reverse()` 反轉，使用 `list_splice(&head_to, temp)` 把 `head_to` 接回 `temp` ，最後更新 `temp` 指向未完成反轉的串列

void q_reverseK(struct list_head *head, int k)
{
    if (list_empty(head) || q_size(head) == 1 || k == 1)
        return;

    int count = 0;

    struct list_head *node, *safe;
    struct list_head *temp = head;

    list_for_each_safe (node, safe, head) {
        count++;
        if (count == k) {
            struct list_head head_to;
            INIT_LIST_HEAD(&head_to);

            list_cut_position(&head_to, temp, node);
            q_reverse(&head_to);
            list_splice_init(&head_to, temp);

            temp = safe->prev;
            count = 0;
        }
    }
}

### `merge_two_list`
宣告一結構參數 `temp` 用來暫存合併結果，當鏈結串列 `L1` 與 `L2` 都不為空時取出各自開頭節點進行比較，較小者會被移動至 `temp` 的尾端。當有一鏈結串列為空時，將另一鏈結串列剩餘的節點全部移動至 `temp` 的尾端，最後將結果從`temp` 移動回 `L1`

void merge_two_list(struct list_head *L1, struct list_head *L2)
{
    struct list_head temp;
    INIT_LIST_HEAD(&temp);

    while (!list_empty(L1) && !list_empty(L2)) {
        element_t *node1 = container_of(L1->next, element_t, list);
        element_t *node2 = container_of(L2->next, element_t, list);
        if (strcmp(node1->value, node2->value) < 0) {
            list_move_tail(&node1->list, &temp);
        } else {
            list_move_tail(&node2->list, &temp);
        }
    }

    if (!list_empty(L1))
        list_splice_tail_init(L1, &temp);
    else
        list_splice_tail_init(L2, &temp);

    list_splice(&temp, L1);
}

### `q_sort`
原始版本 :
採用的排序演算法為 `Bubble Sort` ，時間複雜度為 $O(n^2)$ ，在 `make test` 測試時，trace-14-complexity.cmd 會因為處理時間過久而無法通過檢測

---     trace-14-perf   0/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order
ERROR: Time limit exceeded.  Either you are in an infinite loop, or your code is too inefficient
ERROR: Not sorted in ascending order

void q_sort(struct list_head *head, bool descend)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return;

    for (int i = count; i > 0; i--) {
        struct list_head *cur = head;
        struct list_head *temp = head->next->next->next;
        for (int j = 0; j < i - 1; j++) {
            element_t *node1 = container_of(cur->next, element_t, list);
            element_t *node2 = container_of(cur->next->next, element_t, list);

            if (strcmp(node1->value, node2->value) > 0) {
                cur->next = &node2->list;
                temp->prev = &node1->list;

                node2->list.next = &node1->list;
                node2->list.prev = cur;
                node1->list.next = temp;
                node1->list.prev = &node2->list;
            }

            cur = cur->next;
            temp = temp->next;
        }
    }

    if (descend) {
        q_reverse(head);
    }
}

改進版本 :
採用的排序演算法為 `Merge Sort` ，時間複雜度為 $O(log n)$

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

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

    struct list_head half;
    INIT_LIST_HEAD(&half);
    list_cut_position(&half, head, slow);

    q_sort(&half, descend);
    q_sort(head, descend);
    merge_two_list(head, &half);
}

### `q_ascend` / `q_descend`
`q_ascend` 和 `q_descend` 使用相同的方法，差異只在其中 `strcmp()` 比較節點資訊的是大於還是小於

這裡以 `q_descend` 作範例說明 :
宣告 `cur` 為目前節點、 `temp` 為下一個節點，首先需要先將鏈結串列做反轉，如果當前節點的值比前一個節點小（不符合升序），刪除當前節點直到走訪完整個鏈結串列，最後將鏈結串列再次反轉恢復為原始順序

int q_ascend(struct list_head *head)
{
    int count = q_size(head);
    if (count == 0 || count == 1)
        return count;

    q_reverse(head);

    struct list_head *cur = head->next;
    struct list_head *temp = head->next->next;

    while (temp != head) {
        const element_t *node1 = container_of(cur, element_t, list);
        element_t *node2 = container_of(temp, element_t, list);

        if (strcmp(node1->value, node2->value) < 0) {
            list_del(&node2->list);
            free(node2->value);
            free(node2);
            temp = cur->next;
        } else {
            cur = cur->next;
            temp = temp->next;
        }
    }

    q_reverse(head);

    return q_size(head);
}

### `q_merge`
宣告 `cur` 為第一個佇列，使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_for_each_safe` 走訪所有的佇列，將他們的節點移動到第一個佇列的尾部，並更新第一個佇列的大小（ `size` ），最後根據 `descend` 進行升序或降序排序

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;

    queue_contex_t *q_head = container_of(head->next, queue_contex_t, chain);

    if (q_head->chain.next == q_head->chain.prev)
        return q_head->size;

    struct list_head *cur;
    struct list_head *safe;
    queue_contex_t *cur_queue;

    list_for_each_safe (cur, safe, head) {
        if (cur == &q_head->chain) {
            continue;
        }
        cur_queue = container_of(cur, queue_contex_t, chain);
        list_splice_tail_init(cur_queue->q, q_head->q);
        q_head->size += cur_queue->size;
    }

    q_sort(q_head->q, descend);
    return q_head->size;
}