---
tags: linux, kernel
---

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

## 實驗環境

$ 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:                   43 bits physical, 48 bits virtual
CPU(s):                          16
On-line CPU(s) list:             0-15
Thread(s) per core:              2
Core(s) per socket:              8
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       AuthenticAMD
CPU family:                      23
Model:                           113
Model name:                      AMD Ryzen 7 3700X 8-Core Processor
Stepping:                        0
Frequency boost:                 enabled
CPU MHz:                         2200.000
CPU max MHz:                     4426.1709
CPU min MHz:                     2200.0000
BogoMIPS:                        7186.24
Virtualization:                  AMD-V
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        4 MiB
L3 cache:                        32 MiB
NUMA node0 CPU(s):               0-15

## 針對佇列的操作
### q_new
> commit 7183b8e

初始化 queue

struct list_head *q_new()
{
    struct list_head *tmp;
    tmp->next = tmp;
    tmp->prev = tmp;
    return tmp;
}

> commit c747f08
- 加入防止 head 為 NULL 的情況

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    /* If malloc failed, return NULL. */
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

:::danger
不要只張貼程式碼，要解說和列出後續的改進。
在 GitHub 上都有 commit 提交日期，你不需要在此標注日期。
不要輕易說 "done"，工程總有可持續改進之處。
:notes: jserv
:::

### q_insert_head
> commit 7183b8e

創造一個新的 node 加入整個 queue 的開頭
- 如果成功加入新的 node 會回傳 ture , 反之則回傳 false 。

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

    element_t *tmp_node = malloc(sizeof(element_t));
    tmp_node->value = malloc(sizeof(s));
    memset(tmp_node->value, '\0', s_len);
    strncpy(tmp_node->value, s, strlen(s));
    INIT_LIST_HEAD(&tmp_node->list);
    list_add(&tmp_node->list, head);
    return true;
}

> commit 7e331e1

- 前面的 function 在 implement 的時候 string copy 的時候少算了 '\0'

bool q_insert_head(struct list_head *head, char *s)
{
    int s_len = sizeof(char) * strlen(s) + 1;
    if (!head)
        return false;

    element_t *tmp_node = malloc(sizeof(element_t));
    tmp_node->value = malloc(s_len);
    memset(tmp_node->value, 0, s_len);
    strncpy(tmp_node->value, s, strlen(s) + 1);
    INIT_LIST_HEAD(&tmp_node->list);
    list_add(&tmp_node->list, head);
    return true;
}

> commit 05a5ad4

- 前面的 function 沒有考慮到 malloc 失敗之後要釋放掉所有已經 allocate 的記憶體。

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

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

    int s_len = sizeof(char) * strlen(s) + 1;
    tmp_node->value = malloc(s_len);
    if (!tmp_node->value) {
        q_release_element(tmp_node);
        return false;
    }

    memset(tmp_node->value, 0, s_len);
    strncpy(tmp_node->value, s, strlen(s) + 1);
    INIT_LIST_HEAD(&tmp_node->list);
    list_add(&tmp_node->list, head);
    return true;
}

### q_remove_head
> commit 7183b8e

移除整個 queue 中的第一個 node
- 如果整個 queue 為空，則會回傳 NULL 。（ 由第一個 if 判條件進行判斷 )
- 如果 sp 為 NULL，則會因為無法確定要 remove 的 string 是什麼，所以回傳 NULL 。（ 由第二個 if 判條件進行判斷 )

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head->next == head)
        return NULL;

    if (sp == NULL)
        return NULL;

    element_t *tmp_node = container_of(head->next, element_t, list);
    strncpy(sp, tmp_node->value, bufsize - 1);
    list_del(head->next);
    return tmp_node;
}

> commit c747f08
- 加入 remove head quiet 功能

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

    element_t *tmp_node = container_of(head->next, element_t, list);
    if (sp)
        strncpy(sp, tmp_node->value, bufsize - 1);
    list_del(head->next);
    return tmp_node;
}

> commit 05a5ad4
- truncate 多餘的字元

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

    element_t *tmp_node = container_of(head->next, element_t, list);
    if (sp) {
        /* avoid to delete a string which is longer than the given bufsize */
        strncpy(sp, tmp_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->next);
    return tmp_node;
}

### q_size
> commit 7183b8e

計算目前 queue 中有多少 node
- 回傳值為 queue 中 node 的數量

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_free
> commit 05a5ad4

釋放所有 allocated 的記憶體

void q_free(struct list_head *l)
{
    if (l == NULL)
        return;

    element_t *cur_node = NULL, *next_node = NULL;
    list_for_each_entry_safe (cur_node, next_node, l, list)
        q_release_element(cur_node);
    free(l);
}

### q_delete_mid
> commit 4e06235

刪除正中間的的 node
- 如果整個 queue 為空，則會回傳 false 。（ 由第一個 if 判條件進行判斷 )
- 如果成功刪除會回傳 true ，否則回傳 false 。

:::spoiler 待解決問題
- 需要搞清楚為什麼我們需要多創造出一個 node 來刪除 list_head 的 pointer（ 因為要刪除整個 node ，所以需要一個 pointer 指向整個 node ）
:::

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

    struct list_head *tmp = head->next;
    int counter = 0;
    if (q_size(head) % 2)
        counter = (q_size(head) - 1) / 2;
    else
        counter = q_size(head) / 2;
    for (; counter > 0; counter--) {
        tmp = tmp->next;
    }
    list_del(tmp);
    element_t *tmp_node = container_of(tmp, element_t, list);
    q_release_element(tmp_node);
    return true;
}

### q_remove_tail
> commit 4e06235

移除整個 queue 中的最後一個 node
- 如果整個 queue 為空，則會回傳 NULL 。（ 由第一個 if 判條件進行判斷 )
- 如果 sp 為 NULL，則會因為無法確定要 remove 的 string 是什麼，所以回傳 NULL 。（ 由第二個 if 判條件進行判斷 )

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (head->next == head)
        return NULL;

    if (sp == NULL)
        return NULL;

    element_t *tmp_node = container_of(head->next, element_t, list);
    strncpy(sp, tmp_node->value, bufsize - 1);
    list_del(head->next);
    return tmp_node;
}

> commit 05a5ad4

- truncate 多餘的字元

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

    element_t *tmp_node = container_of(head->prev, element_t, list);
    if (sp) {
        /* avoid to delete a string which is longer than the given bufsize */
        strncpy(sp, tmp_node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(head->prev);
    return tmp_node;
}

### q_insert_tail
> commit 4e06235

創造一個新的 node 加入整個 queue 的結尾。
- 如果成功在尾端加入新的 node 會回傳 ture , 反之則回傳 false 。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (head->prev == head)
        return NULL;

    if (sp == NULL)
        return NULL;

    element_t *tmp_node = container_of(head->prev, element_t, list);
    strncpy(sp, tmp_node->value, bufsize - 1);
    list_del(head->prev);
    return tmp_node;
}

> commit 7e331e1

- 前面的 function 在 implement 的時候 string copy 的時候少算了 '\0'

bool q_insert_tail(struct list_head *head, char *s)
{
    int s_len = sizeof(char) * strlen(s) + 1;
    if (!head)
        return false;

    element_t *tmp_node = malloc(sizeof(element_t));
    tmp_node->value = malloc(s_len);
    memset(tmp_node->value, 0, s_len);
    strncpy(tmp_node->value, s, strlen(s) + 1);
    INIT_LIST_HEAD(&tmp_node->list);
    list_add_tail(&tmp_node->list, head);
    return true;
}

> commit 05a5ad4

- 前面的 function 沒有考慮到 malloc 失敗之後要釋放掉所有已經 allocate 的記憶體。

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

    element_t *tmp_node = malloc(sizeof(element_t));

    if (!tmp_node)
        return false;

    int s_len = sizeof(char) * strlen(s) + 1;
    tmp_node->value = malloc(s_len);
    if (!tmp_node->value) {
        q_release_element(tmp_node);
        return false;
    }

    memset(tmp_node->value, 0, s_len);
    strncpy(tmp_node->value, s, strlen(s) + 1);
    INIT_LIST_HEAD(&tmp_node->list);
    list_add_tail(&tmp_node->list, head);
    return true;
}

### q_reverse
> commit 7e331e1

- 此函式用以反轉佇列所有節點的順序

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

    struct list_head *tmp = NULL, *next = head;
    // swapping the data
    for (; tmp != head; next = tmp) {
        tmp = next->next;
        next->next = next->prev;
        next->prev = tmp;
    }
}

### q_sort
> commit 05a5ad4

此函式透過將最後一筆對 head 的連結打斷，將原本的雙向佇列改為單向，並傳入 merge sort function 進行排序，最後將排序好的 queue 回復為雙向佇列。

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

    struct list_head *cur = NULL;
    head->prev->next = NULL;
    head->next = mergesort(head->next);
    head->next->prev = head;
    list_for_each (cur, head) {
        if (!cur->next) {
            cur->next = head;
            cur->next->prev = cur;
        } else
            cur->next->prev = cur;
    }
}

merge
> commit 05a5ad4

此函式將兩條以排序完的 queue 依照 data 的大小順序合併為一個新的 queue 。
- 回傳值為一個 pointer 指向**合併完成**的 queue 的第一筆資料。

struct list_head *merge(struct list_head *l1, struct list_head *l2)
{
    struct list_head *tmp = NULL, *head = NULL;

    if (strcmp(list_entry(l1, element_t, list)->value,
               list_entry(l2, element_t, list)->value) < 0) {
        tmp = l1;
        head = l1;
        l1 = l1->next;
    } else {
        tmp = l2;
        head = l2;
        l2 = l2->next;
    }

    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) < 0) {
            tmp->next = l1;
            tmp = tmp->next;
            l1 = l1->next;
        } else {
            tmp->next = l2;
            tmp = tmp->next;
            l2 = l2->next;
        }
    }
    if (l1)
        tmp->next = l1;
    if (l2)
        tmp->next = l2;
    return head;
}

mergesort
> commit 05a5ad4

此函式將 queue 中的 data 切割成只包含一筆 data 的 list ，再交由 merge function 將 data 按照大小順序合併。
- 回傳值為一個 pointer 指向**排序完成**的 queue 的第一筆資料
- 為了確保無論何種情況下，排序的時間複雜度皆為 $\operatorname{O}(nlogn)$ ，所以選擇使用 merge sort 演算法進行排序。

struct list_head *mergesort(struct list_head *head)
{
    // merge sort
    if (!head || !head->next)
        return head;

    struct list_head *fast = head->next;
    struct list_head *slow = head;

    // split list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    // sort each list
    struct list_head *l1 = mergesort(head);
    struct list_head *l2 = mergesort(fast);

    // merge sorted l1 and sorted l2
    return merge(l1, l2);
}

:::warning
善用 List APIs 改寫上述程式碼。

使用通順的漢語書寫，日後你在面試場合，可能會不經意說出過去寫下的話語，現在就開始要求！
:notes: jserv
:::
- 在 github 上面通過所有的 test
### q_shuffle

此函式將 queue 中的 data 依照 Fisher–Yates shuffle 演算法隨機 shuffle

- Fisher–Yates shuffle 演算法的優勢在於可以在 $\operatorname{O}(n)$ 的時間複雜度下完成 shuffle

void q_shuffle(struct list_head *head)
{
    srand(time(NULL));

    // 用 q_size 得出整個 queue 的大小
    int len = q_size(head);
    
    // 將 indirect pointer 指向 queue 的第一個 data
    struct list_head **indirect = &head->next;

    while (len) {
        // 決定第幾個 node 要放到 tail 
        int random = rand() % len;
        indirect = &head->next;

        // 找出要放到 tail 的 node
        while (random--)
            indirect = &(*indirect)->next;

        list_move_tail(*indirect, head);
        len--;
    }
}

## Reference
[Merger sort implementation](https://npes87184.github.io/2015-09-12-linkedListSort/)