# 2022q1 Homework1 (lab0)
contribute by < `ChiVincent` >

## 實驗環境

### macOS + [Lima](https://github.com/lima-vm/lima) with Ubuntu 21.10

$ gcc --version
gcc (Ubuntu 11.2.0-7ubuntu2) 11.2.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   36 bits physical, 48 bits virtual
CPU(s):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              1
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      06/9e
Stepping:                        13
CPU MHz:                         2399.904
BogoMIPS:                        4799.80
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        16 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-3

### Ubuntu 20.04 LTS

（WIP）

## 針對佇列的操作

### q_new

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (head == NULL)
        return NULL;

    INIT_LIST_HEAD(head);

    return head;
}

### q_free

void q_free(struct list_head *l)
{
    // When l is NULL, it should not be freed.
    if (l == NULL)
        return;

    struct list_head *pos, *tmp;

    list_for_each_safe (pos, tmp, l) {
        list_del(pos);
        q_release_element(list_entry(pos, element_t, list));
    }

    free(l);
}

### q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    // When head is NULL or given string is invalid, it should not be inserted.
    if (head == NULL || s == NULL)
        return false;

    // Allocate space for new node.
    element_t *e = malloc(sizeof(element_t));
    if (e == NULL)
        return false;

    // Copy string to new node.
    int str_len = strlen(s);
    e->value = malloc(str_len + 1);
    if (e->value == NULL) {
        free(e);
        return false;
    }

    memcpy(e->value, s, str_len);
    e->value[str_len] = '\0';

    // Insert new node at head.
    list_add(&e->list, head);

    return true;
}

- 原本使用 `strdup()` 將 `s` 的內容複製到 `e->value` 中，但這麼做會讓 complexity test 失敗故改成 `malloc` + `memcpy` 的方式

### q_insert_tail

bool q_insert_tail(struct list_head *head, char *s)
{
    // When head is NULL or given string is invalid, it should not be inserted.
    if (head == NULL || s == NULL)
        return false;

    element_t *e = malloc(sizeof(element_t));
    if (e == NULL)
        return false;

    // Copy string to new node.
    int str_len = strlen(s);
    e->value = malloc(str_len + 1);
    if (e->value == NULL) {
        free(e);
        return false;
    }

    memcpy(e->value, s, str_len);
    e->value[str_len] = '\0';

    // Insert new node at tail.
    list_add_tail(&e->list, head);

    return true;
}

### q_remove_head

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

    element_t *e = list_first_entry(head, element_t, list);
    list_del(&e->list);

    if (sp) {
        memcpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return e;
}

- 原本使用 `strcpy` 將 `e->value` 的內容複製到 `sp` 中，但 `strcpy` 會嘗試尋找 NULL Byte 而導致 complexity test 失敗

### q_remove_tail

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

    element_t *e = list_last_entry(head, element_t, list);
    list_del(&e->list);

    if (sp) {
        memcpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    return e;
}

### q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int size = 0;
    struct list_head *pos;
    list_for_each (pos, head)
        size++;

    return size;
}

### q_delete_mid

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

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

    for (; fast != head && fast->next != head;
         fast = fast->next->next, slow = slow->next)
        ;

    struct list_head *mid = slow;
    list_del(mid);
    q_release_element(list_entry(mid, element_t, list));

    return true;
}

- 此處使用 [Floyd's Cycle Detection Algorithm](https://zh.wikipedia.org/zh-tw/Floyd%E5%88%A4%E5%9C%88%E7%AE%97%E6%B3%95) 中的快慢指標技巧尋找中間點

### q_delete_dup

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

    // create garbage colloector
    struct list_head *gc = q_new();
    if (!gc)
        return false;

    bool should_delete = false;
    struct list_head *pos, *next;
    list_for_each_safe (pos, next, head) {
        if (next == head)
            break;
        element_t *e = list_entry(pos, element_t, list),
                  *n = list_entry(next, element_t, list);

        if (strcmp(e->value, n->value) == 0) {
            should_delete = true;
            list_move(pos, gc);
        } else if (should_delete) {
            should_delete = false;
            list_move(pos, gc);
        }
    }

    q_free(gc);

    return true;
}

- 此處宣告了一個 `gc` 用於收集將會被刪除的節點
- 因為題目保證 `dedup` 指令一定是在 `sort` 之後才被執行，理論上這邊還可以優化成將整個具有重複節點的區段直接移到 `gc` 中處理

### q_swap

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    for (struct list_head **indirect = &head->next;
         *indirect != head && (*indirect)->next != head;
         indirect = &(*indirect)->next->next) {
        list_move(*indirect, (*indirect)->next);
    }
}

- 此處利用課程上提到的 `indirect pointer` 實作，有效縮減程式內容

### q_reverse

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    for (struct list_head *pos = head->next; pos != head; pos = pos->prev) {
        struct list_head *tmp = pos->prev;
        pos->prev = pos->next;
        pos->next = tmp;
    }

    struct list_head *last = head->next;
    head->next = head->prev;
    head->prev = last;
}

### q_sort

struct list_head *merge(struct list_head *L1, struct list_head *L2)
{
    struct list_head *head = NULL, **ptr = &head, **cur;
    for (cur = NULL; L1 && L2; *cur = (*cur)->next) {
        element_t *l = list_entry(L1, element_t, list),
                  *r = list_entry(L2, element_t, list);
        cur = (strcmp(l->value, r->value) <= 0) ? &L1 : &L2;
        *ptr = *cur;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}


struct list_head *merge_sort(struct list_head *head)
{
    if (!head->next)
        return head;

    struct list_head *slow = head, *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next, slow = slow->next)
        ;

    struct list_head *mid = slow->next;
    slow->next = NULL;

    return merge(merge_sort(head), merge_sort(mid));
}

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    head->prev->next = NULL;
    head->next = merge_sort(head->next);

    struct list_head *ptr = head;
    for (; ptr->next; ptr = ptr->next)
        ptr->next->prev = ptr;
    ptr->next = head;
    head->prev = ptr;
}

- 分成三個函式實作
- `q_sort`：既有的 API 進入點
- `merge_sort`：主要的 Merge Sort 實現邏輯
- `merge`：將左、右兩個 Linked List 合併
- `q_sort` 會將 Circular Linked List 拆解成一條 Singular Linked List（以 `NULL` 結尾）
- 最後會將其修復
- `merge_sort` 利用快慢指標分別將一條 Linked List 拆解為兩條（左、右）
- `merge` 根據傳入的左、右 Linked List，經過比較將其合併回去
- 可改善的部份
- 不打斷 Circular Linked List，改以 Indirect Pointer 的方式實作