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

:::danger
注意作業書寫規範！
:notes: jserv
:::

## 環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           94
Model name:                      Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz
Stepping:                        3
CPU MHz:                         3400.000
CPU max MHz:                     4000.0000
CPU min MHz:                     800.0000
BogoMIPS:                        6799.81
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-7

## 開發過程 queue.c
### q_new

struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q)
        INIT_LIST_HEAD(q);
    return q;
}

- 使用 `malloc` 分配一塊記憶體給 `list_head`
- 如果成功分配就會使用 [`INIT_LIST_HEAD`](#INIT_LIST_HEAD) 來初始化

### q_free

void q_free(struct list_head *l)
{
    if (l) {
        element_t *e, *safe;

        list_for_each_entry_safe (e, safe, l, list) {
            q_release_element(e);
        }

        free(l);
    }
}

- 如果 `l` 為 `NULL` 不做事
- 使用 [`list_for_each_entry_safe`](#list_for_each_entry_safe) 走訪所有元素
- 並使用[`q_release_element`](#q_release_element)刪除

#### q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

- 刪除 `element_t`

### q_insert_head

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

    element_t *item = q_alloc_element(s);
    if (!item)
        return false;

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

- 如果 `head` 為 `NULL` 回傳 `false`
- 使用 [`q_alloc_element`](#q_alloc_element) 分配記憶體給 `item` ，分配失敗則回傳 `false`
- 使用 [`list_add`](#list_add) 將 `item` 插入 `head` 的前端

#### q_alloc_element

element_t *q_alloc_element(char *s)
{
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return NULL;

    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return NULL;
    }
    INIT_LIST_HEAD(&e->list);

    return e;
}

- 使用 `malloc` 分配記憶體，如果失敗回傳 `NULL`
- 使用 `strdup` 分配記憶體給 `value` ，並複製進去，如果失敗回傳 `NULL`
- 使用 [`INIT_LIST_HEAD`](#INIT_LIST_HEAD) 初始化

### q_insert_tail

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

    element_t *item = q_alloc_element(s);
    if (!item)
        return false;

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

- 與 [`q_insert_head`](#q_insert_head) 大致相同
- 差別於使用 [`list_add_tail`](#list_add_tail) 將 `item` 插入 `head` 的尾端

### 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 *item = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    if (sp) {
        strncpy(sp, item->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return item;
}

- 判斷 `head` 是 `NULL` 或是使用 [`list_empty`](#list_empty) 判斷為空佇列回傳 `NULL`
- `head->next`
- 使用 [`list_entry`](#list_entry) 取出 `element_t`
- 使用 [`list_del_init`](#list_del_init) 刪除並初始化節點

### q_size

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

    struct list_head *node;
    int count = 0;
    list_for_each (node, head)
        count++;

    return count;
}

- 使用 [`list_for_each`](#list_for_each) 來歷遍所有節點並計數

### q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

    if (!head || list_empty(head))
        return false;

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

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

    list_del(mid);
    q_release_element(list_entry(mid, element_t, list));

    return true;
}

- 用兩個指標一個快 `fast` 一個慢 `mid`
- 快的速度為慢的兩倍，所以只要 `fast` 到尾端的時， `mid` 就會位於中間
- 再使用 `list_del` 與 `q_release_element` 將 `mid` 從 list 中移除與釋放記憶體空間
:::warning
考慮到 circular doubly-linked list 的特性，可以怎樣改進實作？
:notes: jserv
:::

### q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || list_empty(head))
        return false;
    struct list_head *ptr1 = head->next, *ptr2 = head->next->next;

    while (ptr2 != head) {
        bool flage = false;
        element_t *node1, *node2;

        node1 = list_entry(ptr1, element_t, list);
        node2 = list_entry(ptr2, element_t, list);

        while (!strcmp(node1->value, node2->value)) {
            flage = true;
            ptr2 = ptr2->next;
            q_release_element(node2);
            if (ptr2 == head)
                break;

            node2 = list_entry(ptr2, element_t, list);
        }
        if (flage) {
            ptr1 = ptr1->prev;
            q_release_element(node1);
        }
        ptr1->next = ptr2;
        ptr2->prev = ptr1;

        ptr1 = ptr2;
        if (ptr2 != head)
            ptr2 = ptr2->next;
    }
    return true;
} 

- 有兩個指標 `ptr1`, `ptr2`
- `ptr1` 為前一個 `ptr2`
- 當兩個指標的 `value` 一樣的話， `flage` 就會立起並且 `ptr2` 就會繼續往前直到與 `ptr1` 的直不同或是到尾端。
- 使用 [`q_release_element`](#q_release_element) 刪除
- 如果 `flage` 被立起來 `ptr1` 就會往前一個並與 `ptr2` 相接。

### q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/

    if (!head || list_empty(head))
        return;

    struct list_head *ptr = head->next;
    while (ptr != head && ptr->next != head) {
        list_swap(ptr, ptr->next);
        ptr = ptr->next;
    }
}

- 把 `ptr` 與 `ptr->next` 使用 `list_swap` 交換
- 因為 `ptr` 被換到前面了所以只需要在往下一個走一步就可以了

### q_reverse

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

    struct list_head *current = head->next, *tmp;

    while (current != head) {
        tmp = current->prev;
        current->prev = current->next;
        current->next = tmp;
        current = current->prev;
    }

    tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
}

- 只要把原本的 `prev` 與 `next` 調換就可以反轉

### q_sort

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

    struct list_head *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->prev->next = NULL;

    struct list_head *left, *right, *merge, *ptr;
    left = merge_sort(head);
    right = merge_sort(slow);

    element_t *node1, *node2;

    node1 = list_entry(left, element_t, list);
    node2 = list_entry(right, element_t, list);
    if (strcmp(node1->value, node2->value) <= 0) {
        merge = left;
        left = left->next;
    } else {
        merge = right;
        right = right->next;
    }
    ptr = merge;
    while (left && right) {
        node1 = list_entry(left, element_t, list);
        node2 = list_entry(right, element_t, list);

        if (strcmp(node1->value, node2->value) <= 0) {
            ptr->next = left;
            left = left->next;
        } else {
            ptr->next = right;
            right = right->next;
        }
        ptr = ptr->next;
    }
    if (left) {
        ptr->next = left;
    }

    if (right) {
        ptr->next = right;
    }

    return merge;
}

void q_sort(struct list_head *head)
{
    if (!head || !head->next)
        return;

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

    struct list_head *front = head, *behind = head->next;
    while (behind) {
        behind->prev = front;
        front = behind;
        behind = behind->next;
    }

    front->next = head;
    head->prev = front;
}

- 先斷開 double-linked 把 list 當作單向的來處理
- 所以在每一次遞迴都會做 `slow->prev->next = NULL` 來斷開雙向
- 再來就是一般的 merge sort 並在最後重現把 `prev` 連回去

## Functions in list.h

### INIT_LIST_HEAD
- Initialize an unlinked list node.

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

### list_for_each_entry_safe
- The current node (iterator) is allowed to be removed from the list.
- Any other modifications to the the list will cause undefined behavior.

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

## qtest.c

### shuffle

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

    srand(time(NULL));

    for (int i = cnt; i > 0; i--) {
        int index = rand() % i;
        struct list_head *tmp = head->next;

        for (int j = 0; j < index; j++)
            tmp = tmp->next;

        list_del(tmp);
        list_add_tail(tmp, head);
    }
}

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l)
        report(3, "Warning: Calling reverse on null queue");
    error_check();

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    set_noallocate_mode(false);
    show_queue(3);
    return !error_check();
}

參考了 `do_reverse` 來新增了新的 command
並把 shuffle 實做於 `q_shuffle`
- 隨機的取一個 `index`
- 並把位於那個位置的元素插入尾端