---
tags: linux2022
---

# 2022q1 Homework1 (lab0)
contributed by < `naihsin` >

## 實驗環境

$ 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):                          4
On-line CPU(s) list:             0-3
Thread(s) per core:              2
Core(s) per socket:              2
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           61
Model name:                      Intel(R) Core(TM) i5-5257U CPU @ 2.70GHz
Stepping:                        4
CPU MHz:                         3099.851
CPU max MHz:                     3100.0000
CPU min MHz:                     500.0000
BogoMIPS:                        5399.73
Virtualization:                  VT-x
L1d cache:                       64 KiB
L1i cache:                       64 KiB
L2 cache:                        512 KiB
L3 cache:                        3 MiB
NUMA node0 CPU(s):               0-3

## 作業要求
依據上述指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
queue.c 僅提供介面 (interface) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
- q_new: 建立新的「空」佇列;
- q_free: 釋放佇列所佔用的記憶體;
- q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
- q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
- q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
- q_release_element: 釋放特定節點的記憶體空間;
- q_size: 計算目前佇列的節點總量;
- q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List
- q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II
- q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs
- q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
- q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法;

## 開發紀錄
### q_new
- 先 malloc 一塊記憶體空間給 head
- 若 malloc 失敗則 return NULL
- 接著把 head 的兩個指標 next, prev 初始化，兩個指標皆指向自己

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

    return head;
}

### q_free
- 判斷 queue 的 head(也就是 ```l``` )是否為空
- 若 ```l``` 為空，則代表「沒有」佇列
- 若 ```l``` 不為空，此時佇列有兩種狀態，分別是「空」佇列與「不是空」佇列(也就是佇列裡面有 element )
- 使用 ```list_for_each_entry_safe``` 走訪所有包含 list_head 結構的 element entry
- 使用 ```q_release_element``` 把每一個 element free 掉
- 最後別忘了還要把 ```l``` free 掉

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

### q_insert_head
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return false
- malloc ```element_t``` 大小給 ptr 指標
- 判斷 malloc 是否有成功
- 若 malloc 失敗則 return false
- 使用 ```list_add``` 把 ptr 指向 list 成員的位址加入到 list head
- 接著 malloc ```strlen(s) + 1``` 大小給 ptr->value ，包含空字元
- 判斷 malloc 是否成功
- 把 ```s``` 複製到新的 element 中

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

    element_t *ptr = (element_t *) malloc(sizeof(element_t));
    if (!ptr)
        return false;

    list_add(&ptr->list, head);

    ptr->value = (char *) malloc(strlen(s) + 1);
    if (!ptr->value)
        return false;

    strncpy(ptr->value, s, strlen(s) + 1);

    return true;
}

### q_insert_tail
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return false
- malloc ```element_t``` 大小給 ptr 指標
- 判斷 malloc 是否有成功
- 若 malloc 失敗則 return false
- 使用 ```list_add``` 把 ptr 指向 list 成員的位址加入到 list tail
- 接著 malloc ```strlen(s) + 1``` 大小給 ptr->value ，包含空字元
- 判斷 malloc 是否成功
- 把 ```s``` 複製到新的 element 中

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

    element_t *ptr = (element_t *) malloc(sizeof(element_t));
    if (!ptr) {
        return false;
    }

    list_add_tail(&ptr->list, head);

    ptr->value = (char *) malloc(strlen(s) + 1);
    if (!ptr->value)
        return false;

    strncpy(ptr->value, s, strlen(s) + 1);

    return true;
}

### q_remove_head
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return NULL
- 判斷 list 是否為空
- 若為空則 return NULL
- 用 ```list_entry``` 找到從 head 數來的第一個 element entry 的位址
- 判斷 sp 字串是否為空
- 若為空，把 element 的字串複製到 sp 中
- 記得要把 sp padding 一個空字元
- 用 ```list_del_init``` 把剛剛找到的 element 的 list 成員 從 list 中移除
- 把找到的 element return 回去

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

    element_t *ptr = list_entry(head->next, element_t, list);

    if (sp) {
        strncpy(sp, ptr->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del_init(&ptr->list);

    return ptr;
}

### q_remove_tail
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return NULL
- 判斷 list 是否為空
- 若為空則 return NULL
- 用 ```list_entry``` 找到從 tail 數來的第一個 element entry 的位址
- 判斷 sp 字串是否為空
- 若為空，把 element 的字串複製到 sp 中
- 記得要把 sp padding 一個空字元
- 用 ```list_del_init``` 把剛剛找到的 element 的 list 成員 從 list 中移除
- 把找到的 element return 回去

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

    element_t *ptr = list_entry(head->prev, element_t, list);

    if (sp) {
        strncpy(sp, ptr->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del_init(&ptr->list);

    return ptr;
}

### q_release_element
- 在 ```q_insert_head```, ```q_insert_tail``` 中，分別 malloc 整個 ```element``` 結構與 ```element->value``` ，使用到兩次 malloc ，在釋放 element 也必須把這兩個結構 free 掉

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

### q_size
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return 0
- 用 ```list_for_each``` 走訪 list 所有的節點
- ```list_for_each``` 是一個 macro ，展開為

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

- 設置 len 變數，算出總共有幾個節點
- return len 回去

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
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return false
- 判斷 queue 是否為空
- 若 queue 為空則 return false
- 接著設置快慢指針，找到中間的節點，快指針一次走兩步，慢指針一次走一步，當快指針到達終點時，慢指針才走完一半，所以可以利用這種特性來找到中間的節點
- 使用 ```list_del_init``` 把慢指針從 list 中移除
- 用 ```list_entry``` 找到慢指針被存放到 element 結構的位址
- 用 ```q_release_element``` 把找到的 element release

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || !q_size(head))
        return false;

    struct list_head *slow = head->next, *fast = head->next;
    while (fast->next != head->next && fast->next->next != head->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_del_init(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

### q_delete_dup
- 判斷 queue 是否為空
- 若為空則 return false
- 設置 cur 指針來走訪每個節點
- 當 cur->next == head 則代表已經走訪完一圈
- 設置 first, second 來紀錄相鄰兩個節點所處的 element 結構的位址
- 當 first->value 跟 second->value 的值相等，則把 second 移除，且把 cur->next 從 list 中移除
- 當 first->value 跟 second->value 的值不相等，把 cur 設置成 cur->next ，繼續下一對相鄰節點比較

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!q_size(head))
        return false;

    struct list_head *cur = head->next;
    while (cur->next != head) {
        element_t *first = list_entry(cur, element_t, list);
        element_t *second = list_entry(cur->next, element_t, list);
        if (!strcmp(first->value, second->value)) {
            list_del_init(cur->next);
            q_release_element(second);
        } else {
            cur = cur->next;
        }
    }
    return true;
}

### q_swap
- 設置 left, right 紀錄相鄰的兩個節點
- 當 left == head || right == head 則代表已經走訪完一圈的所有節點
- 使用 ```list_move``` 把 left 節點從 list 中移除，且再把 left 加入到 right 在 list 中的下一個位址，如此一來就可以達成 swap 兩個節點的操作
- 更新 left = left->next, right = left->next，繼續下一輪的 swap 操作

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    struct list_head *left = head->next, *right = left->next;
    while (left != head && right != head) {
        list_move(left, right);
        left = left->next;
        right = left->next;
    }
}

### q_reverse
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return
- 使用 ```list_for_each_safe``` 走訪 list 中的所有節點
- 用 ```list_move``` 刪除節點

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

    struct list_head *li, *safe;
    list_for_each_safe (li, safe, head) {
        list_move(li, head);
    }
}

:::warning
若為 singular，不需要繼續處理。
:notes: jserv
:::

### q_sort
- 這邊我選擇用 divide and conquer 的方式來實做程式
- 判斷 head 是否為空(也就是判斷有沒有佇列)
- 若沒有佇列則 return
- 判斷 list 是否為空
- 若為空則 return
- 先把 head->prev->next 設成 NULL ，讓最後一個節點的 next 指向 NULL，方便設置後續 ```q_merge``` 的結束條件
- 呼叫 ```q_merge``` 來切割節點直到剩下一個節點
- 接著 ```q_merge``` 會回傳已經排序好的節點
- 此時的 queue 並不是完整的 doubly linked-list
- while 是找到回傳 list 的最後一個節點
- 復原 head 與 最後一個節點的關係

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

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

### q_merge
- 判斷 ptr->next 是否為空
- 若為空則代表已經切割至剩下一個節點，return ptr
- 使用快慢指針來找到中間節點，詳細說明可參考 ```q_delete_mid```
- 從中間節點切割左右兩邊的 list
- 使用 recursive ，再次把左邊的 list 切割，直到切割到剩下一個節點
- 使用 recursive ，再次把右邊的 list 切割，直到切割到剩下一個節點
- 使用 ```q_mergefinal``` 把左邊與右邊的 list 排序合併

struct list_head *q_merge(struct list_head *ptr)
{
    if (!ptr->next)
        return ptr;

    struct list_head *slow = ptr, *fast = ptr;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    struct list_head *left, *right;
    fast = slow->next;
    slow->next = NULL;
    left = q_merge(ptr);
    right = q_merge(fast);
    return q_mergefinal(left, right);
}

### q_mergefinal
- 這邊使用到 ```pointer to pointer``` 目的是為了減少記憶體的分配
- 設置 head 指標紀錄排序好的第一個節點， head 先指向 left (也就是左邊節點)
- 設置指標的指標 ```**ptr``` ，讓 ptr 紀錄 head 的記憶體位址，以便根據要修改當前節點的記憶體位址來變更 ptr
- 設置 prev 指標紀錄前一個節點， 以便讓下一個節點的 prev 指回前一個節點
- 設置指標的指標 ```**node``` ，讓 node 紀錄即將要加入 list 的節點的記憶體位址，一開始設成 NULL
- 使用 for 迴圈直到 left 跟 right 皆不為 NULL
- 使用 ```list_entry``` 找到 left 跟 right 所在的 element 結構的記憶體位址
- 比較 el->value (左節點)跟 el2->value (右節點)的 element value
- 若 el->value (左節點)比較小，則把 node 設成 ```&left``` 也就是 left 節點所處的記憶體位址
- 反之，則把 node 設成 ```&right``` 也就是 right 節點所處的記憶體位址
- 接著把 ```*node->prev = prev``` 也就是把 ```left->prev = prev``` 或 ```right->prev = prev``` ，把 node 與前一個節點的關係接上
- 更新 prev ，把 prev 設成當前節點 *node
- 更新 *ptr ，把當前要修改的記憶體位址的節點設成 *node
- 前幾個步驟，已經順利把節點接上，接著要更新 ptr ，把紀錄當前節點的記憶體位址移到下一個節點
- 更新 *node ，把當前指向 left 或 right 的節點更新為 left->next 或 right->next ， 等價於 ```left = left->next```

struct list_head *q_mergefinal(struct list_head *left, struct list_head *right)
{
    struct list_head *head = left, *prev = NULL, **ptr = &head, **node;

    for (node = NULL; left && right; *node = (*node)->next) {
        element_t *el = list_entry(left, element_t, list);
        element_t *el2 = list_entry(right, element_t, list);
        node = (strcmp(el->value, el2->value) < 0) ? &left : &right;
        (*node)->prev = prev;
        prev = *node;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = left ? left : right;
    (*ptr)->prev = prev;
    return head;
}