# 2023q1 Homework1 (lab0)
contributed by < `HCCFish` >

## 開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.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):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4999.90
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    6 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

## 開發過程

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::

### q_new

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

其中`free(q);`參考[@25077667](https://hackmd.io/@25077667/lab0-2023#q_new)的所提到的問題，即使配置記憶體錯誤，在沒有 explicitly deallocate space 的情況下 free 比較保險。
:::warning
何謂「比較保險」？依據是什麼？請討論。
:notes: jserv
:::

### q_free

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        q_release_element(entry);
    }
    free(l);
}

使用`list_for_each_entry_safe`一個個節點訪其中的 element，且避免釋放 entry 後，無法往下一個節點前進。用`q_release_element`來釋放 element。

### q_insert_head

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *new_element = malloc(sizeof(element_t));
    if (!new_element) {
        free(new_element);
        return false;
    }
    size_t len = strlen(s);
    new_element->value = strdup(s);
    new_element->value[len] = '\0';
    list_add(&new_element->list, head);
    return true;
}

前面加`free`的想法與`q_new`一樣，`strdup`再複製字串的功能下同時可以配置原字串大小+1byte的記憶體，只是沒有特別定義為多少，所以要再設為`\0`符合題目(不確定有沒有必要)。
:::warning
TODO: 討論 null terminator 的操作
:notes: jserv
:::

### q_insert_tail
用與`q_insert_head`相同的方法，使用`list_add_tail`來代替`list_add`

### 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 *head_element = list_first_entry(head, element_t, list);
    if (sp != NULL) {
        strncpy(sp, head_element->value, bufsize);
        sp[bufsize - 1] = '\0';
    }
    list_del(&head_element->list);
    return head_element;
}

此處有要求將節點內的字串複製到 sp 還有設定長度 所以用`strncpy`來複製字串,並在字串最後一個 byte 給 `\0`.
:::warning
「並在字串最後一個 byte 給0」說法不精準，請改進。
留意 `\0` 和 '0' 的差異
:notes: jserv
:::

### q_remove_tail
用與`q_remove_head`相同的方法，使用`list_last_entry`來代替`list_first_entry`
### q_size

int q_size(struct list_head *head)
{
    if (!head) {
        return -1;
    }
    struct list_head *cur;
    int len = 0;
    list_for_each (cur, head) {
        len++;
    }
    return len;
}

善用`list.h`中的`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 || !head->next)
        return false;
    struct list_head *slow = head, *fast = head->next->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast != head) {
        slow->next = slow->next->next;
    }
    element_t *mid = list_entry(slow->next, element_t, list);
    list_del(&mid->list);
    q_release_element(mid);
    return true;
}

用`Fast & Slow Pointer`的方法實作來找到中間的節點，而`if (fast != head) `其實就是`fast->next == head`的情況，也就是有偶數個節點會發生的情形，要選`slow->next->next`才是函數要求的中間節點.

### q_reverse

    list_for_each_safe (cur, safe, head) {
        list_move(cur, head);

參考[@komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverse-%E5%AF%A6%E4%BD%9C)的實作方法，透過將每一個節點依序移到前面，最後就會達到 reverse 的效果.
### q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || k < 2)
        return;
    struct list_head *cur, *safe, *tmp_head = head;
    LIST_HEAD(dummy);
    int i = 1;
    list_for_each_safe (cur, safe, head) {
        if (i == k) {
            list_cut_position(&dummy, tmp_head, cur);
            q_reverse(&dummy);
            list_splice_init(&dummy, tmp_head);
            i = 0;
            tmp_head = safe->prev;
        }
        i++;
    }
    q_free(&dummy);
}

參考[@komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverseK-%E5%AF%A6%E4%BD%9C)的實作方法，定義一條新佇列, 專門用來暫存擷取下來特定長度的節點並執行`q_reverse`執行完再接回去原本的 list, 只是`komark06`的最後忘記釋放佇列的空間，用`q_free`補上
### q_swap

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;
    struct list_head *first, *second;
    for (struct list_head *cur = head->next; cur != head && cur->next != head;
         cur = cur->next) {
        first = cur;
        second = cur->next;
        first->next = second->next;
        second->next = first;
        second->prev = first->prev;
        first->prev = second;
    }
}

一開始想說直接`return q_reverseK(head, 2)`就好，後來想到更簡潔的作法.
`cur`在 for loop 內 swap 的過程中也會變成指向第二的節點, 所以只要`cur = cur->next`移到下一個節點就好。
### q_sort
參考去年範例[＠kdnvt](https://hackmd.io/byNYeoGvQv-a9TNDc2CKFQ?both#q_sort)的方法, 其中最後一個方法很有趣，活用了 doubly-linked list 雙向連接的特性，在排序的過程中，暫時只用 singly-linked list的方式連接，而多出的 link 則指向 sorted list 的尾端節點，此方法不需要額外的記憶體空間來記錄 sorted list 的位置。