# 2023q1 Homework1 (lab0)
contributed by < [ctc2324](https://github.com/ctc2324) >

## 開發環境

$ 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:         36 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  2
  On-line CPU(s) list:   0,1
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz
    CPU family:          6
    Model:               58
    Thread(s) per core:  1
    Core(s) per socket:  2
    Socket(s):           1
    Stepping:            9
    BogoMIPS:            6784.59

本次實驗暫時使用虛擬機器安裝 GNU/Linux 來進行。

:::warning
virtual machine 應翻譯為「虛擬機器」，避免只寫「機」，後者將無法區分 engine 一詞。
:notes: jserv
:::

## 開發過程
### q_new實作

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

    return newhead;
}

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

為新的佇列產生一個 `newhead` 節點，且 `prev` 及 `next` 皆指向自身。若 `malloc` 失敗，則回傳 `NULL` 提醒使用者 `newhead` `malloc` 失敗。

### 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` 來代替迴圈往下個節點移動。直到變成空佇列，再釋放開頭的記憶體 `l`。
### q_insert_head及q_insert_tail實作
#### q_inser_head

bool q_insert_head(struct list_head head, char s)
{
    if(!head)
        return false;
    element_t *newnode = malloc(sizeof(*newnode));
    if(!newnode)
        return false

    size_t slen = strlen(s)+1;
    newnode->value = malloc(slen * sizeof(char));

    memcpy(newnode->value,s,slen);
    list_add(newnode->list,head);
    return true;
}

#### q_inser_tail

bool q_insert_tail(struct list_head head, char s)
{
   if(!head)
        return false;
    element_t *newnode = malloc(sizeof(*newnode));
    if(!newnode)
        return false

    size_t slen = strlen(s)+1;
    newnode->value = malloc(slen * sizeof(char));

    memcpy(newnode->value,s,slen);
    list_add_tail(&newnode->list,head);
    return true;

}

基本程式碼相同，差別在於 `q_insert_head` 使用函式 `list_add`，`q_insert_tail` 使用 `list_add_tail` 。
先 `malloc` 一個 `newnode` ，並且檢查是否 `malloc` 成功。

在 queue.h 中定義 element_t 中註解提到
>value needs to be explicitly allocated and freed

因此在中間為 value 額外申請空間，考慮到 string 最後為 `'\0'` ，字串長度需額外增加 1。
最後將輸入字串複製到 `newnode->value` 中，並且將 `&newnode->list` 及 `head` 輸入函式 `list_add` 中。

:::success
在make test後發現測試 `malloc` 是否成功的項目沒有通過，才發現上面的程式碼忘記加入檢查 `newnode->value` 的 `malloc` 是否成功的判斷式。

if(!(newnode->value)){
    free(newnode);
    return false;
}

加入判斷式後，成功通過檢查 `malloc` 的測試。
:::

### q_remove_head及q_remove_tail實作
#### q_remove_head

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

    struct list_head *node = head->next;
    if (node == head)
        return NULL;

    element_t *rem = list_entry(node, element_t, list);
    int len = strnlen(rem->value, bufsize - 1);
    memcpy(sp, rem->value, len);
    (sp + len  sizeof(char)) = '\0';

    list_del(node);
    return rem;
}

#### q_remove_tail

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

    struct list_head *node = head->prev;
    if (node == head)
        return NULL;

    element_t *el = list_entry(node, element_t, list);
    int len = strnlen(el->value, bufsize - 1);
    memcpy(sp, el->value, len);
    (sp + len  sizeof(char)) = '\0';

    list_del(node);

    return el;
}

### q_size實作

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

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

基本上與老師在牛刀小試中的程式碼無異。

### q_delete_mid實作

bool q_delete_mid(struct list_head *head)
{
    if(!head || list_empty(head))
        return false;
    int mid = (q_size(head)/2)+1;

    for(int i=0;i<mid;i++){
        head = head->next;
    }

    element_t *del;
    list_del(head);
    del = list_entry(head,element_t,list);
    q_release_element(del);

    return true;
}

從 `q_size` 中找到整個queue的節點數量，在計算出位於中間的節點。透過 `for` 迴圈將指標移動到要刪除的中間節點，並且使用 `list_del` 及 `q_release_element` 進行節點的 delete 。

### q_delete_dup實作

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

    struct list_head now = head->next, next = now->next;
    bool dup = false;

    while (now != head && next != head) {
        element_t *now_entry = list_entry(now, element_t, list);
        element_t *next_entry = list_entry(next, element_t, list);

        while (next != head && !strcmp(now_entry->value, next_entry->value)) {
            list_del(next);
            q_release_element(next_entry);
            next = now->next;
            next_entry = list_entry(next, element_t, list);
            dup = true;
        }

        if (dup) {
            list_del(now);
            q_release_element(now_entry);
            dup = false;
        }

        now = next;
        next = now->next;
    }
    return true;
}

設定 `now` 、 `next` 兩個指標。並且同時設置 `now_entry` 、 `next_entry` 兩個 `elemen_t` 結構的指標比對 value 值。
當進入第二個 `while` 迴圈時代表節點有重複，將 `next` 的點刪除，並將 `dup` 這個布林變數設為 `true` 。當遇到不重複時，迴圈結束。此時若 `dup` 為 `true` 表示剛剛有處理過重複節點，此時要將重複節點的最一開始的點也刪除，也就是 `now` 。

### q_swap實作

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *p = head->next;
    struct list_head *q;

    while(p != head && p->next != head){
        q = p->next;
        list_move(p,q);
        p = p->next;
    }
}

`swap` 需要將節點倆倆互換，搜尋 `list.h` 後發現可以使用 `list_move` 函式進行實作。將前後兩點輸入至 `list_move` 把後點插入前點之前完成兩點互換順序。以此類推直到指標繞回起點，當 `p` 指向 `head` 或 `p->next` 指向 `head` (節點為奇偶數的差別)，則代表已經繞完一圈，完成 `swap` 的過程。

### q_reverse實作

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

    struct list_head *now,*safe,*tmp;
    list_for_each_safe(now,safe,head){
        tmp = now->prev;
        now->prev = now->next;
        now->next = tmp;
    }
    tmp = head->prev;
    head->prev = head->next;
    head->next = tmp;
}

使用 `list_for_each_safe` 來確保在更改 `next` 及 `prev` 順序後還能往下走到未更改的下個點。藉此來走訪各點完成 reverse 。
最後再將頭尾順序對調，使 `head` 指向原本的尾端。

### q_reverseK 實作

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

    struct list_head now, safe, *tmp = head;
    LIST_HEAD(rev);
    int cnt = k;
    list_for_each_safe (now, safe, head) {
        cnt--;
        if (cnt == 0) {
            list_cut_position(&rev, tmp, now);
            q_reverse(&rev);
            list_splice(&rev, tmp);
            cnt = k;
            tmp = safe->prev;
        }
    }
}

使用 `list_for_each_safe` 來確保能往下走到尾端，並且透過 `cnt` 來計數走了幾格，當 `cnt == 0` 時表示到了要 reverse 的節點了，則運用 `list_cut_position` 將這段 link-list 切出來，並且丟到前面寫好的 `q_reverse` 中處理，處理完後使用 `list_splice` 接回本來的link-list。最後將 `cnt` 值重設，並且將指標 `tmp` 指向 `safe->prev` 來做為下一次翻轉後接回的節點。
### q_sort 實作
使用 `merge sort` 實作，但在開始前要先將 queue 的 double-linklist 改成單向， sort 完再回到雙向。

void q_sort(struct list_head *head) {
    if(!head || list_empty(head))
         return;
    head->prev->next = NULL;
    head->next = merge_sort(head->next);

    //back to double link-list
    struct list_head *prev = NULL,*now = head;

    while(now){
        now->prev = prev;
        prev = now;
        now = now->next;
    }
    head->prev = prev;
    prev->next = head;
}

struct list_head merge_sort(struct list_head head){

    if(!head || !head->next)
        return head;

    struct list_head *fast,*slow = head,*mid;

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

    mid = slow->next;
    slow->next = NULL;

    struct list_head *left = merge_sort(head);
    struct list_head *right = merge_sort(mid);

    return merge(left,right);
}

此處使用 fast 及 slow 指標來快速找到每次傳入的 `link-list` 的中間點。並將左右兩邊依次輸入函式 `merge` 中來把兩個串列併在一起。

struct list_head merge(struct list_head l1, struct list_head *l2)
{
    struct list_head head = NULL, *ptr = &head, **node;
    for (node = NULL; l1 && l2; node = (node)->next) {
        node = (strcmp(list_entry(l1, element_t, list)->value,
                       list_entry(l2, element_t, list)->value) < 0)
                   ? &l1
                   : &l2;
        ptr = node;
        ptr = &(*ptr)->next;
    }
    if (l1)
        *ptr = l1;
    else
        *ptr = l2;
    return head;
}

這邊參考了課程講義 [你所不知道的 C 語言: linked list 和非連續記憶體中的案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)使用的 indirect pointer 技巧。
### q_descend 實作

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    int size = 0;
    struct list_head *now = head->prev;
    while (now != head) {
        size++;
        if (now->prev == head)
            break;
        element_t *now_entry = list_entry(now, element_t, list);
        element_t *prev_entry = list_entry(now->prev, element_t, list);

        if (strcmp(now_entry->value, prev_entry->value) > 0) {
            list_del(&prev_entry->list);
            q_release_element(prev_entry);
            size--;
        } else {
            now = now->prev;
        }
    }
    return size;
}

從尾端開始比較，若在左邊某點 `A` 小於現在的節點 `now` ，表示在 `A` 右邊的節點 `now` 大於 `A` ，因此 A 應該要被刪除。
### q_merge 實作

### 完成進度
:::info
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_inser_tail
- [x] q_remove_head
- [x] q_remove_tail
- [x] q_size
- [x] q_delete_mid
- [x] q_delete_dup
- [x] q_swap
- [x] q_reverse
- [x] q_reverseK
- [x] q_sort
- [x] q_descend
- [ ] q_merge
:::
## Make test分數
:::warning
Total 95(89)/100(本機測試為89分 github 為95分)

> 不用急著說「持續努力中」這樣空泛的話，人在做，Google/GitHub 在看，拿出成果再說。
> :notes: jserv
:::
:::info
:SMILE:：了解！
:::