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;
}

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

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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 。

待解決問題

需要搞清楚為什麼我們需要多創造出一個 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 的第一筆資料
為了確保無論何種情況下，排序的時間複雜度皆為
$O (n l o g n)$ ，所以選擇使用 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);
}

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

使用通順的漢語書寫，日後你在面試場合，可能會不經意說出過去寫下的話語，現在就開始要求！

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

jserv

在 github 上面通過所有的 test

q_shuffle

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

Fisher–Yates shuffle 演算法的優勢在於可以在
$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

2022q1 Homework1 (lab0)

實驗環境

針對佇列的操作

q_new

q_insert_head

q_remove_head

q_size

q_free

q_delete_mid

q_remove_tail

q_insert_tail

q_reverse

q_sort

q_shuffle

Reference

Read more

2022q1 Homework3 (quiz3)

2022q1 Homework3 (fibdrv)

2022q1 Homework4 (quiz04)

2022q1 Homework2 (quiz2)