2022q1 Homework1 (lab0)

contributed by < Chao-Shun-Cheng >

實驗環境

$ 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):                          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-8700K CPU @ 3.70GHz
Stepping:                        10
CPU MHz:                         3700.000
CPU max MHz:                     4700.0000
CPU min MHz:                     800.0000
BogoMIPS:                        7399.70
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 : 建立新的「空」佇列
• 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 : 以遞增順序來排序鏈結串列的節點

開發過程

queue.c 實作

queue 資料結構

從 queue.h 當中的 element_t 可以知道 Node 的資料結構包含一個 value 與 list 。其中 value 會指向一個字串，另外 list 則是會定義在 list.h 裡的一種資料結構。可以看到 list 有兩個指標分別指向下一個與上一個 Node 的 list。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

完整的 queue 資料結構如下圖所示。

q_new

new 需要先透過 malloc 進行記憶體配置，再透過 list.h 所提供的 INIT_LIST_HEAD 去進行初始化。

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

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

q_free

首先要判斷 queue 裡面是否存在節點，可以利用 list.h 提供的 list_empty 去判斷。如果有 Node 再利用 list_first_entry 去得到指向包含這個 list 的 element。最後再利用 q_release_element 去釋放 Node 的記憶體。

void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (!list_empty(l)) {
        element_t *target = list_first_entry(l, element_t, list);
        list_del(l->next);
        q_release_element(target);
    }
    free(l);
}

其中 list_first_entry 是利用 container_of 去獲得 Node 的記憶體位置，詳細使用方法與原理可以參考 Linux 核心原始程式碼巨集: container_of。

q_insert_head

首先要先利用 malloc 去分配 Node 所需要的記憶體空間，再去分配 value 所需要的空間，最後再利用 list.h 所提供的 list_add 將 Node 插入 queue 當中。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *newh = malloc(sizeof(element_t));
    if (!newh)
        return false;
    int len = strlen(s);
    newh->value = malloc(sizeof(char) * (len + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);
    list_add(&newh->list, head);
    return true;
}

q_insert_tail

與 q_insert_head 方法雷同，不同的是利用 list_add_tail 去插入佇列中。

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *newh = malloc(sizeof(element_t));
    if (!newh)
        return false;
    int len = strlen(s);
    newh->value = malloc(sizeof(char) * (len + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);
    list_add_tail(&newh->list, head);
    return true;
}

q_remove_head

首先透過 list_first_entry 去獲得指向第一個 Node 的指標，再透過 list_del 去將 Node 移出 queue。需要特別注意的是 value 與 bufsize 的大小，以及結尾字元 \0。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head) || !sp)
        return NULL;
    element_t *target = list_first_entry(head, element_t, list);
    list_del(head->next);
    int len = strlen(target->value);
    if (len > (bufsize - 1)) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    } else {
        strncpy(sp, target->value, len);
        sp[len] = '\0';
    }
    return target;
}

q_remove_tail

與 q_remove_head 雷同，不過是透過 list_last_entry 去獲得指向最後一個 Node 的指標。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head) || !sp)
        return NULL;
    element_t *target = list_last_entry(head, element_t, list);
    list_del(head->prev);
    int len = strlen(target->value);
    if (len > (bufsize - 1)) {
        strncpy(sp, target->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    } else {
        strncpy(sp, target->value, len);
        sp[len] = '\0';
    }
    return target;
}

q_size

這邊是直接用 list_for_each 走訪全部節點以計算數量。還在思考如何降低計算時間。

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *node = NULL;
    int size = 0;
    list_for_each (node, head) {
        size++;
    }
    return size;
}

q_delete_mid

宣告兩個指標 next_node 與 prev_node 用 while 分別從 queue 的前與後去走，當 prev_node == next_node 或 next_node->next == prev_node 就代表找到中間的 Node 了。

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *next_node = head->next, *prev_node = head->prev;
    while (next_node != prev_node && next_node->next != prev_node) {
        next_node = next_node->next;
        prev_node = prev_node->prev;
    }
    element_t *target = list_entry(prev_node, element_t, list);
    list_del(prev_node);
    q_release_element(target);
    return true;
}

q_delete_dup

這題主要是參考 LeetCode 82. Remove Duplicates from Sorted List II 這題的內容來實作，不過在原題目中是有重複的要全部 delete ，因此我透過 list_for_each_safe 去看每個 Node 的值，並將值用 value 指標指著，再透過strcmp(value, target->value) == 0 來去判斷鄰近的 Value 是不是一樣，是的話就 delete ，直到遇到不一樣為止。

Case one : 沒有遇到相同

value 直接可以指到下一個值

Case two : 有遇到相同

delete 後面重複出現的之後，還要再刪掉自己本身

Version one
考慮刪掉自己本身的 Node ，但發現 trace-06 一直過不了。

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    struct list_head *node = NULL, *safe = NULL;
    bool dup = false;
    char *value = NULL;
    element_t *target = NULL;
    list_for_each_safe (node, safe, head) {
        target = list_entry(node, element_t, list);
        if (strcmp(value, target->value) == 0) {  // duplicates
            list_del(node);
            q_release_element(target);
            dup = true;
        } else {
            value = target->value;
            if (dup) {
                target = list_entry(node->prev, element_t, list);
                list_del(node->prev);
                q_release_element(target);
                dup = false;
            }
        }
    }
    return true;
}

Version two
於是嘗試不刪掉自己本身，指刪掉後面一樣的 Node ，竟然神奇的過了。不確定是不是我對題目有誤解還是有甚麼 Bug 。

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;
    bool dup = false;
    char *value = NULL;
    element_t *entry = NULL, *safe = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (value && strcmp(value, entry->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
            dup = true;
        } else {
            value = entry->value;
            if (dup) {
                // target = list_entry(entry->list.prev, element_t, list);
                // list_del(&target->list);
                // q_release_element(target);
                dup = false;
            }
        }
    }
    return true;
}

q_swap

swap 這邊是利用 from 與 to 兩個指標分別去紀錄要 swap 兩個 Node 的前後關係，再透過 while 去把所有需要 swap 的 Node 進行相關的指標替換即可。

void q_swap(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return;
    struct list_head *node = head->next, *from = NULL, *to = NULL, *next = NULL;
    while ((node != head) && (node->next != head)) {
        next = node->next;
        from = node->prev;
        to = node->next->next;
        from->next = next;
        next->prev = from;
        next->next = node;
        node->prev = next;
        node->next = to;
        to->prev = node;
        node = to;
    }
}

q_reverse

這邊的想法是直接將 prev 與 next 兩個指標的內容交換即可。因此直接透過 list_for_each_safe 去把每個 Node 裡的 prev 與 next 內容交換。

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

q_sort

這邊是利用 mergesort 下去進行排序，並透過 LIST_HEAD 將變數放在 stack 裡，就不用特別去思考如何釋放記憶體的議題。雖然測資可以通過，但當我要 git commit 時發現，queue.h 不能修改。會去研讀 list_sort.c 並進一步思考如何修改。

後來發現將 Function 放在 q_sort 上面就可以直接使用，不用特別在宣告在 queue.h 裡面，總算可以順利 git commit 了。

mergesort 主要有兩個重點，分別是將 list 切開以及合併，合併這邊參考 LeetCode 21. Merge Two Sorted Lists 的思考下去實作。

void mergetwolist(struct list_head *head1,
                  struct list_head *head2,
                  struct list_head *head)
{
    if (!head || !head1 || !head2 || (list_empty(head1) && list_empty(head2)))
        return;
    if (list_empty(head1)) {
        list_splice_tail_init(head2, head);
        return;
    }
    if (list_empty(head2)) {
        list_splice_tail_init(head1, head);
        return;
    }
    struct list_head *temp = NULL, *l1 = head1->next, *l2 = head2->next;
    while (l1 != head1 && l2 != head2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) > 0) {
            temp = l2;
            l2 = l2->next;
            list_move_tail(temp, head);
        } else {
            temp = l1;
            l1 = l1->next;
            list_move_tail(temp, head);
        }
    }
    list_splice_tail_init(head1, head);
    list_splice_tail_init(head2, head);
}

切分的部分則是利用區域變數的特性，離開函式會自動釋放記憶體的優勢，來去進行實作。

void mergesort(struct list_head *head, int size)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    LIST_HEAD(head1);
    LIST_HEAD(head2);
    int mid = size >> 1, count = 0;
    struct list_head *node = NULL, *safe = NULL;
    list_for_each_safe (node, safe, head) {
        count++;
        if (count == mid) {
            list_cut_position(&head1, head, node);
            list_splice_tail_init(head, &head2);
            break;
        }
    }
    mergesort(&head1, mid);
    mergesort(&head2, size - mid);
    mergetwolist(&head1, &head2, head);
}

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

make test 自動評分

---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
---	trace-05-ops	6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
---	trace-06-ops	6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
---	trace-07-string	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
---	trace-10-robust	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
---	trace-13-malloc	6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

花了一些時間與參考許多同學的實作方式，總算是看到皮卡丘了 QAQ

文字訊息不要用螢幕截圖展現，你的讀者可能是視障朋友，而且圖片無助於資料檢索。

jserv

已經修正，感謝老師提醒