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

:::danger
未見 [cin-cout/lab0-c](https://github.com/cin-cout/lab0-c) 程式碼更新。
:notes: jserv
:::

## 開發環境

$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.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):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
Stepping:                        10
CPU MHz:                         1201.821
CPU max MHz:                     4500.0000
CPU min MHz:                     800.0000
BogoMIPS:                        5199.98
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        12 MiB
NUMA node0 CPU(s):               0-11

## 開發過程
### q_new
#### version 1
<s>很多人會</s> 宣告 element 再傳其中的 head 給 qtest，但其實 qtest 是<s>餵給</s> q_context_t 內的 q ，所以 malloc element 的大小只會浪費空間，free 也會需要多 free head 所在的 element。

:::danger
避免說「餵給」這樣不精準的話。「很多人」如何如何，到底跟你的開發進度何關？
:notes: jserv
:::

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

### q_insert_head
#### version 1

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q)
        return false;
    strcpy(q->value, s);
    q->list.prev = NULL;
    q->list.next = head;
    head->prev = &q->list;
}

#### version 2
<s>一開始耍白痴</s>，忘記剛創立時 q->value 是 NULL ，不能 copy 。
加了空間宣告。
:::warning
避免帶有個人色彩的發言，改進你的漢語表達。
:notes: jserv
:::

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        return false;
    }
    q->value = malloc(sizeof(s));
    strcpy(q->value, s);
    list_add(&q->list, head);
    return true;
}

#### version 3
評分時發現11 12怎麼過不了明明已經做完了 insert 了，後來發現是動態宣告 value 的時候沒有檢查是否有足夠空間。
養成良好 coding 習慣，要檢查任何：
1. 傳入值是否有意義
2. 動態宣告是否有成功

bool q_insert_head(struct list_head *head, char *s)
{
    if(!head || !s){
        return false;
    }
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        return false;
    }
    q->value = malloc(sizeof(s));
    if (!(q->value)) {
        free(q);
        return false;
    }
    strcpy(q->value, s);
    list_add(&q->list, head);
    return true;
}

#### version 4
之前的方式是切跟 char s 一樣的 size ，但其實只要切跟字串一樣剛剛好大小就好了。

bool q_insert_head(struct list_head *head, char *s)
{
    if(!head){
        return false;
    }
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        return false;
    }
    int s_len = strlen(s);
    q->value = malloc(s_len+1);
    if (!(q->value)) {
        test_free(q);
        return false;
    }
    strncpy(q->value, s, s_len);
    q->value[s_len] = '\0';
    list_add(&q->list, head);
    return true;
}

### q_insert_tail
#### version 1
這是跟 insert head 一起做的，前者成功， insert tail <s>照本宣科</s>。
:::warning
查閱教育部辭典「[照本宣科](https://dict.revised.moe.edu.tw/dictView.jsp?ID=115527)」的寓意，再回來看這裡程式碼的撰寫，看用語是否恰當。
:notes: jserv
:::

bool q_insert_tail(struct list_head *head, char *s)
{   
    if(!head){
        return false;
    }
    element_t *q = malloc(sizeof(element_t));
    if (!q) {
        return false;
    }
    int s_len = strlen(s);
    q->value = malloc(s_len+1);
    if (!(q->value)) {
        test_free(q);
        return false;
    }
    strncpy(q->value, s, s_len);
    q->value[s_len] = '\0';
    list_add_tail(&q->list, head);
    return true;
}
}

:::warning
思考如何精簡程式碼。
:notes: jserv
:::

### q_remove_head
#### version 1

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{   
    if(!head || !sp){
        return NULL;
    }
    element_t * cur_r = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, cur_r->value, bufsize);
    return cur_r;
}

#### version 2
加了 sp[bufsize-1] = '\0'; ，其實不影響成績，但是這是考慮若 value size > bufsize 時在最底端會沒有 '\0' 結束符號，所以加了這行。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{   
    if(!head || !sp){
        return NULL;
    }
    element_t* cur_r = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, cur_r->value, bufsize);
    sp[bufsize-1] = '\0';
    return cur_r;
}

#### version 3
參考之前範例，在 empty 下不會把 head 刪掉。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{   
    if(!head || !sp || list_empty(head)){
        return NULL;
    }
    element_t* cur_r = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    strncpy(sp, cur_r->value, bufsize);
    sp[bufsize-1] = '\0';
    return cur_r;
}

#### version 4
參考 [chun61205](https://hackmd.io/@roger61205/lab0-2023) ，原作法對 sp 的處理有問題，若 sp 傳 NULL 只代表 test 不需要用到 sp 來做一些輸出，還是要 remove node ，原作法是將 sp == NULL 視為無效。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{   
    if(!head || list_empty(head)){
        return NULL;
    }
    element_t* cur_r = list_entry(head->next, element_t, list);
    list_del_init(head->next);
    if(sp){
        strncpy(sp, cur_r->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    return cur_r;
}

### q_remove_tail
#### version 1
同上，<s>照本宣科</s>

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head || list_empty(head)){
        return NULL;
    }
    element_t* cur_r = list_entry(head->prev, element_t, list);
    list_del_init(head->prev);
    if(sp){
        strncpy(sp, cur_r->value, bufsize-1);
        sp[bufsize-1] = '\0';
    }
    return cur_r;
}

### q_delete_mid
#### version 1
最後 error，time limit exceeded。

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* slow = head->next;
    struct list_head* fast = head->next;
    while(fast != head || fast != head->prev){
        slow = slow->next;
        fast = fast->next->next;
    }
    //del slow
    list_del_init(slow);
    q_free(slow);
    return true;
}

#### version 2
while 條件打錯了，應該是&&不是||

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* slow = head->next;
    struct list_head* fast = head->next;
    while(fast != head && fast != head->prev){
        slow = slow->next;
        fast = fast->next->next;
    }
    //del slow
    list_del_init(slow);
    q_free(slow);
    return true;
}

### q_size
#### version 1
這很簡單，原本想試看看可不可以類似 container_of 的作法直接去找 queue_context_t 的 size ，但以失敗告終。

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if(!head){
        return 0;
    }
    int len = 0;
    struct list_head *node;
    list_for_each(node, head)
        len++;
    return len;
}

### q_free
#### version 1

void q_free(struct list_head *l) {
    struct list_head *node;
    struct list_head *safe;
    element_t* cur_f;
    list_for_each_safe(node, safe, l){
        cur_f = list_entry(node, element_t, list);
        free(cur_f);
    }
    INIT_LIST_HEAD(l);
}

#### version 2
加了防呆，目前認為以前有些人的 queue free 做的有問題。
在 qtest 內 head 是放在 queue_context_t 裡面，而 qtest 再 q_free 後也會把 queue_context_t 給 free 掉，所以 qfree 應該是不需要處理 head 的。
:::warning
改進漢語表達。
:notes: jserv
:::

void q_free(struct list_head *l) 
{
    if(!l){
        return;
    }
    struct list_head *node;
    struct list_head *safe;
    element_t* cur_f;
    list_for_each_safe(node, safe, l){
        cur_f = list_entry(node, element_t, list);
        free(cur_f);
    }
}

#### version 3
用 q_release_element 會比較快，而且舊方法沒有刪掉 value 值。

void q_free(struct list_head *l) 
{
    if(!l){
        return;
    }
    struct list_head *node;
    struct list_head *safe;
    element_t* cur_f;
    list_for_each_safe(node, safe, l){
        cur_f = list_entry(node, element_t, list);
        q_release_element(cur_f);
    }
}

#### version 4
清掉 head 。

void q_free(struct list_head *l) 
{
    if(!l){
        return;
    }
    struct list_head *node;
    struct list_head *safe;
    element_t* cur_f;
    list_for_each_safe(node, safe, l){
        cur_f = list_entry(node, element_t, list);
        q_release_element(cur_f);
    }
    //cur_f = list_entry(l, element_t, list);
    test_free(l);
}

### q_reverse
#### version 1
用 for_each_safe 不用擔心更改以後 next 會不照原本方向，所以就是把每個點都 prev next 交換。

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

#### version 2
原方法沒有處理到 head。

void q_reverse(struct list_head *head) 
{
    if(!head){
        return;
    }
    struct list_head *node;
    struct list_head *safe;
    struct list_head *tmp;
    list_for_each_safe(node, safe, head){
        tmp = node->prev;
        node->prev = node->next;
        node->next = tmp;
    }
    tmp = head->prev;
    head->prev = head->next;
    head->next = tmp;
}

### q_sort
#### version 1
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 對原本雙向的 list 為了配合上課所學單向 merge sort 所作的修改，以及[上課講義](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)對 sort list 的講解，在加上自己的一些<s>優化</s> 改進。

struct list_head* merge_two_queue(struct list_head *L1, struct list_head *L2)
{
    struct list_head* head, **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) ? &L2: &L1;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *)(void *)((uintptr_t)(void *) L1 | (uintptr_t)(void *) L2);
    return head;
}

static struct list_head *merge_sort(struct list_head *head)
{
    if(!head || !head->next){
        return head;
    }
    struct list_head *slow = head, *fast = head->next;
    for (; fast && fast->next; fast = fast->next->next, slow = slow->next)
        ;
    fast = slow->next;
    slow->next = NULL;
    return merge_two_queue(merge_sort(head), merge_sort(fast));
}

/* Sort elements of queue in ascending order */
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* tmp;
    for(tmp=head; tmp->next; tmp=tmp->next){
        tmp->next->prev = tmp;
    }
    tmp->next = head;
    head->prev = tmp;
 }

### q_merge
#### version 1
參考 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 對 queue context 資料結構的理解，以及[上課講義](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)對 merge k sorted list 的講解，改進原本 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C)改為每看一個 queue 就 merge sort 一次，並非先全部<s>串街</s> ??? 再 merge sort。

int q_merge(struct list_head *head)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || list_empty(head))
        return 0;
    queue_contex_t *f_q = list_entry(head->next, queue_contex_t, chain);
    if (list_is_singular(head))
        return f_q->size;
    queue_contex_t *cur_q;
    list_for_each_entry(cur_q, head, chain) {
        if (cur_q != f_q) {
            q_merge_two_sorted(f_q->q, cur_q->q);
            f_q->size += cur_q->size;
            cur_q->size = 0;
        }
    }
    return f_q->size;
}

:::danger
程式碼的縮排和風格，務必依循 [CONTRIBUTING.md](https://github.com/sysprog21/lab0-c/blob/master/CONTRIBUTING.md) 規範。
:notes: jserv
:::

#### version 2
前一版沒有考慮使用 merge_two_queue 時 queue 必須先做前後處理。

@@ -7,12 +7,21 @@ int q_merge(struct list_head *head)
     if (list_is_singular(head))
         return f_q->size;
     queue_contex_t *cur_q;
+    f_q->q->prev->next = NULL;
     list_for_each_entry(cur_q, head, chain) {
         if (cur_q != f_q) {
-            q_merge_two_sorted(f_q->q, cur_q->q);
+            cur_q->q->prev->next = NULL;
+            f_q->q->next = merge_two_queue(f_q->q->next, cur_q->q->next);
+            INIT_LIST_HEAD(cur_q->q);
             f_q->size += cur_q->size;
             cur_q->size = 0;
         }
     }
+    struct list_head* tmp;
+    for(tmp=f_q->q; tmp->next; tmp=tmp->next){
+        tmp->next->prev = tmp;
+    }
+    tmp->next = f_q->q;
+    f_q->q->prev = tmp;
     return f_q->size;
 }

:::info
提示: 使用 `diff -up` 命令可產生二個檔案間的變更處列表
:notes: jserv
:::

### q_reverseK
#### version 1

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if(!head || list_empty(head)){
        return;
    }
    struct list_head *node, *safe, *tmp_head, *tmp;
    int cur_k = 1;
    list_for_each_safe(node, safe, head){
        if(k==1){
            for (int i = 1; i < k; i++) {
                tmp = node->next;
                if(tmp == head){
                    return;
                }
            }
            tmp_head = node;
        }
        else{
            if(cur_k == k){
                cur_k=0;
            }
            else{
                cur_k++;
            }
            list_move(node, tmp_head);
        }
    }

#### version 2
cur_k 條件判斷有誤，然後 move 邏輯修正。

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if(!head || list_empty(head)){
        return;
    }
    struct list_head *node, *safe, *tmp_head = head->next, *tmp;
    int cur_k = 1;
    list_for_each_safe(node, safe, head){
        if(cur_k==1){
            tmp = node;
            for (int i = 1; i < k; i++) {
                tmp = tmp->next;
                if(tmp == head){
                    return;
                }
            }
            tmp_head = node;
        }
        else{
            list_move_tail(node, tmp_head);
            tmp_head = node;
        }
        if(cur_k == k){
            cur_k=1;
        }
        else{
            cur_k++;
        }
    }
}

### q_delete_dup
#### version 1

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if(!head){
        return false;
    }
    struct list_head *node;
    bool last_del = 0;
    list_for_each(node, head){
        if(strcmp(list_entry(node, element_t, list)->value, list_entry(node->next, element_t, list)->value)){
            if(last_del){
                last_del = 0;
                node = node->prev;
                list_del(node->next);
                q_release_element(list_entry(node->next, element_t, list));
            }
        }
        else{//same
            list_del(node->next);
            q_release_element(list_entry(node->next, element_t, list));
            node = node->prev;
            last_del = 1;
        }
    }
    return true;
}

#### version 2

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if(!head){
        return false;
    }
    struct list_head *cur = head;
    while(cur->next != head && cur->next->next != head){
        element_t *c = list_entry(cur->next, element_t, list),
                  *n = list_entry(cur->next->next, element_t, list);
        if(!strcmp(c->value, n->value)){
            while(cur->next->next != head && !strcmp(c->value, n->value)){
                struct list_head *next = n->list.next;
                list_del(cur->next->next);
                q_release_element(n);
                n = list_entry(next, element_t, list);
            }
            list_del(cur->next);
            q_release_element(c);
        }
        cur = cur->next;

    }
    return true;

}