---
# System prepended metadata

title: 2023q1 Homework1 (lab0)
tags: [linux2023]

---

---
tags: linux2023
---

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

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔。
:notes: jserv
:::
:::success
謝謝老師，有進行修改了
:::

## 開發環境
```shell
$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            13
    CPU max MHz:         4500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            5199.98
```

## 開發過程
### q_new
```c
struct list_head *q_new()
{
    struct list_head *head = (struct list_head*) malloc(sizeof(*head));
    if (!head)
        return NULL;

    INIT_LIST_HEAD(head);
    return head;
}
```

### q_free
```c
void q_free(struct list_head *l) {
    if(!l)
        return;
    element_t *save, *temp;

    list_for_each_entry_safe(temp, save, l, list)
        q_release_element(temp);
    free(l);
}
```

### q_insert_{head,tail}
這邊曾經遇到的問題是沒有預留 `'/0'` 位置給 value，導致出現
```
ERROR: Corruption detected in block with address 0x55a707abb980 when attempting to free it
```

目前還沒找到是哪裡產生這樣的訊息，不過解決方法就是在 malloc 時多加一個 byte 的空間

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

    element_t *new = (element_t*) malloc(sizeof(element_t));
    if (!new)
        return false;
    
    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);//+1 for '/0'
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add(&new->list, head);


    return true;
}
```

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

    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add_tail(&new->list, head);
    return true;
}
```

### q_remove_head、q_remove_tail
遇到的問題類似，以q_remove_head為例
:::warning
查詢教育部辭典「[蠻](https://dict.revised.moe.edu.tw/dictView.jsp?ID=1235)」，改進你的漢語書寫。
:notes: jserv
:::
:::success
收到！
:::

```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head)
        return NULL;
    
    sp = (char*) malloc(bufsize * sizeof(char*));
    if(!sp)
        return NULL;
    element_t* first_entry = list_first_entry(head, element_t, list);

    strncpy(sp, first_entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';

    list_del(head->next);
    return first_entry;
}
```

原本這麼寫，但會跑出
> ERROR: Failed to store removed value

後來發現sp已經malloc過了(q_test.c裡do_remove的remove)，再malloc一次會在測試時找不到原本的位置，所以將malloc刪掉就好了
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if(!head)
        return NULL;
    if(!sp)
        return NULL;
        
    element_t* last_entry = list_last_entry(head, element_t, list);
    strncpy(sp, last_entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
    list_del(head->next);
    return last_entry;
}
```

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

    char *value = (char*) malloc(strlen(s) * sizeof(char) + 1);
    if(!value)
        return false;
    
    strcpy(value, s);
    new->value = value;
    list_add_tail(&new->list, head);
    return true;
}
```

### q_swap
```c
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    for(struct list_head* node = head->next; node->next != head; node = node->next){
        list_del(node);
        list_add(node, node->next);
    }
}
```

### q_delete_mid
利用老師上課提到的『指標一快一慢』的方法（Hare & Tortoise Algorithm）
```c
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    // Hare & Tortoise Algorithm
    struct list_head *fast, *slow;
    fast = slow = head->next;
    do{
        fast = fast->next;
        if(fast == head)
            break;
        slow = slow->next;
        fast = fast->next;
    }while(fast != head);
    list_del(slow);
    return true;
}
```

### q_sort
> 參考 [npes87184's blog](https://npes87184.github.io/2015-09-12-linkedListSort/)的作法，再以自己的方法實作

為了實作 merge sort，我加入了兩個函式:
*  `struct list_head *merge_two_lists` : 用來合併二個鏈結串列
* `struct list_head *merge_sort` : merge sort 的遞迴式

merge_two_lists 原本是這麼做的
```c
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
    struct list_head *temp = (struct list_head *)malloc(sizeof(temp));
    if(!temp)
        return list1;
    struct list_head *save = temp;
    while(list1 && list2){
        element_t *v1 = list_entry(list1, element_t, list);
        element_t *v2 = list_entry(list2, element_t, list);
        if(strcmp(v1->value, v2->value) >= 0){
            temp->next = list1;
            list1->prev = temp;
            temp = list1 = list1->next;
        }
        else{
            temp->next = list2;
            list2->prev = temp;
            temp = list2 = list2->next;
        }
    }
    if(!list1){
        temp->next = list2;
        list2->prev = temp;
    } 
    if(!list2){
        temp->next = list1;
        list1->prev = temp;
    } 
    free(temp);
    return save->next;
```

但當我 make test 時會顯示
> FATAL ERROR: Calls to malloc disallowed

發現它不讓我使用 malloc，思來想去找不到好方法，於是尋找是否有人用類似的方法。結果找到 [@seasonwang](https://hackmd.io/@seasonwang/B1B0lVqpo#q_sort) 和我參考的是同一個部落格，而且是用 indirect pointer 的方式，於是我將他的基礎上改進程式碼（減少一個 indirect pointer ），並改為

:::warning
請查詢英文字典，理解 "optimize" 和 "improve" 的差異。
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::

```c
struct list_head *merge_two_lists(struct list_head *list1, struct list_head *list2)
{
    struct list_head *temp = NULL;
    struct list_head **indirect = &temp;
    struct list_head *last = NULL;
    while (list1 && list2) {
        element_t *v1 = list_entry(list1, element_t, list);
        element_t *v2 = list_entry(list2, element_t, list);
        if (strcmp(v1->value, v2->value) <= 0) {
            list1->prev = *indirect;
            *indirect = list1;
            list1 = list1->next;
        } else {
            list2->prev = *indirect;
            *indirect = list2;
            list2 = list2->next;
        }
        last = *indirect;
        indirect = &((*indirect)->next);
    }
    if (!list1) {
        last->next = list2;
        list2->prev = last;
    }
    if (!list2) {
        last->next = list1;
        list1->prev = last;
    }
    return temp;
}
```

然後是遞迴的 merge sort
```c
struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;

    struct list_head *fast, *slow;
    fast = slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    slow->prev->next = NULL;
    slow->prev = NULL;
    struct list_head *list1 = merge_sort(head);
    struct list_head *list2 = merge_sort(slow);
    
    return merge_two_lists(list1, list2);
}
```

再來是作業的 q_sort，當時忘記重新連結頭跟尾，debug 了很久
```c
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
    if(list_empty(head))
        return;
    // break the list circle
    head->prev->next = NULL;
    head->prev = NULL;
    // merge sort
    head->next = merge_sort(head->next);
    // reconnect
    head->next->prev = head;
    struct list_head *t = head;
    while (t->next != NULL) {
        t->next->prev = t;
        t = t->next;
    }
    head->prev = t;
    t->next = head;
}
```

### q_merge
我第一眼看到這個函式時，蠻疑惑為什麼會需要 merge多個 list，因為之前操作都是只有一個 list 的情形。於是閱讀了 ```qtest.c``` 的 ```do_merge``` 和 ```do_new``` 才發現一直以來操作的其實是 ```current->q```。
而在 ```do_merge``` 呼叫 ```q_merge``` 時會傳入 ```&chain.head```，並接收 merge 完後   list 的長度。所以要存取所有的 list 的話，需要用到 ```queue_context_t``` 這個 struct。
```c
int q_merge(struct list_head *head)
{
    
    if(!head || list_empty(head))
        return 0;
    
    queue_contex_t *headchain = list_entry(head->next, queue_contex_t, chain);
    if(list_is_singular(headchain->q))
        return headchain->size;

    for(struct list_head *h = head->next->next; h != head; h = h->next){
        queue_contex_t *qctx = list_entry(h, queue_contex_t, chain);
        headchain->size += qctx->size;
        list_splice_tail_init(qctx->q, headchain->q);
    }
    q_sort(headchain->q);
    return headchain->size;
    // https://leetcode.com/problems/merge-k-sorted-lists/
}
```

### q_descend

[2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/)
![](https://i.imgur.com/8aC1Dnm.png)
:::warning
改以 Graphviz 製圖
:notes: jserv
:::

最直觀的解法應該是從頭開始逐一節點檢查，但是這樣時間複雜度會是 $O(n^{2})$。我觀察之後發現可以由最後一個 node 往前 traverse，遇到 value 比較小的直接 delete 掉，如此時間複雜度就變為 $O(n)$
```c
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;

    int len = 1;
    element_t *t = list_entry(head->prev, element_t, list);
    char *v = t->value;
    struct list_head *h, *safe;
    for(h = head->prev->prev, safe = h->prev; h != head; h = safe, safe = h->prev){
        t = list_entry(h, element_t, list);
        if(strcmp(v, t->value) > 0){
            list_del(h);
            q_release_element(list_entry(h, element_t, list));
        }
        else{
            v = t->value;
            len++;
        }
    }
    return len;
}
```

### q_reverse、q_reverseK
二者非常類似，我都是將 traverse 到的點用        ```list_move``` 移到head後面，比較不同的是 q_reverseK 需要額外用一個 counter 計數以及 head 的位置要調整而已
```c
void q_reverse(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head)
        list_move(node, head);
}
```

```c
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_is_singular(head))
        return;
    struct list_head *node, *safe, *start;
    
    start = head;
    int counter = 0;
    list_for_each_safe(node, safe, head){
        counter++;
        if(counter == k){
            struct list_head *temp, *temp_safe;
            for(temp = start->next, temp_safe = temp->next; temp != safe; temp = temp_safe, temp_safe = temp->next)
                list_move(temp, start);
            counter = 0;
            start = safe->prev;
        }
    }
}
```

目前95/100