2022q1 Homework1 (lab0)

contributed by < zxcj04 >

作業要求

實驗環境

$ 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):                          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:                       AuthenticAMD
CPU family:                      23
Model:                           1
Model name:                      AMD Ryzen 5 1600 Six-Core Processor
Stepping:                        1
Frequency boost:                 enabled
CPU MHz:                         1377.939
CPU max MHz:                     3200.0000
CPU min MHz:                     1550.0000
BogoMIPS:                        6387.35
Virtualization:                  AMD-V
L1d cache:                       192 KiB
L1i cache:                       384 KiB
L2 cache:                        3 MiB
L3 cache:                        16 MiB
NUMA node0 CPU(s):               0-11

開發紀錄

q_new

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

q_free

逐一走訪鏈結串列的節點前，先檢查輸入的指標是否有效。
由於涉及到 list entry 的 delete 以及 node 的 remove 因此使用list_for_each_entry_safe
一開始忽略了 entry 中的 value 也需要 free 所以卡了一陣子。

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

    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        free(entry->value);
        free(entry);
    }
    free(l);
}

q_insert_head

對 Linux 核心風格的 circular doubly-linked list 不夠熟悉。看了〈你所不知道的 C 語言: linked list 和非連續記憶體〉及其錄影兩遍後才感覺有點理解這種設計的思路。
使用 Linux 核心風格 API 的程式碼是在參考了 @jasperlin1996-q_insert_head 的方法後寫出來。

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

    element_t *node = (element_t *) malloc(sizeof(element_t));
    if (!node)
        return false;
    size_t len = strlen(s) + 1;
    node->value = (char *) malloc(sizeof(char) * len);
    if (!node->value) {
        free(node);
        return false;
    }
    strncpy(node->value, s, len);

    LIST_HEAD(list);
    node->list = list;
    list_add(&node->list, head);
    return true;
}

q_remove_head

逐一走訪鏈結串列的節點前，先檢查輸入的指標是否有效以及串列中是否存在節點。
使用 strnlen 以確保即將被複製的字串長度為 bufsize

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

    element_t *del_entry = list_first_entry(head, element_t, list);
    size_t len = strnlen(del_entry->value, bufsize - 1) + 1;
    strncpy(sp, del_entry->value, len);

    list_del(&del_entry->list);
    return del_entry;
}

後來發現不需要使用 strnlen 來檢查長度
只要用 strncpy 並在字串結尾補上 \0 即可
(參考 @laneser 及 @japerlin1996 的筆記)

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

    element_t *del_entry = list_first_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, del_entry->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(&del_entry->list);
    return del_entry;
}

q_remove_tail

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

    element_t *del_entry = list_last_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, del_entry->value, bufsize);
        sp[bufsize - 1] = '\0';
    }

    list_del(&del_entry->list);
    return del_entry;
}

q_delete_mid

使用了 〈你所不知道的 C 語言: linked list 和非連續記憶體〉中的快慢指標技巧找到中間的節點，並從串列中刪除後釋放記憶體。

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

    struct list_head *slow = head->next, *fast = head->next;
    while (fast != head && fast->next != head) {
        slow = slow->next;
        fast = fast->next->next;
    }

    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));

    return true;
}

q_swap

這邊我原本是先取的要交換的兩個節點，並且去調整前後節點的 next 以及 prev 來完成交換。
但覺得不太優雅，因此在參考了 @laneser 的作法後發現實際上是作一樣的動作，但可以利用 Linux 核心風格 API 來簡化程式碼。

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;

    struct list_head *now;
    for (now = head->next; now != head && now->next != head; now = now->next) {
        struct list_head *next = now->next;
        list_del(now);
        list_add(now, next);
    }
}

q_delete_dup

一開始誤會題意，以為是要把重複的留下一個，仔細看過後發現要把所有重複的節點都刪掉會有點麻煩，嘗試過用一個 flag 來辨別，也試過用另一個字串來紀錄重複的字串，最後還是選擇使用 flag 的方式，會繼續思考有沒有辦法簡化現在的程式碼。

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

    element_t *now, *next;
    bool is_dup = false;
    list_for_each_entry_safe (now, next, head, list) {
        if (now->list.next != head && strcmp(now->value, next->value) == 0) {
            list_del(&now->list);
            q_release_element(now);
            is_dup = true;
        } else if (is_dup) {
            list_del(&now->list);
            q_release_element(now);
            is_dup = false;
        }
    }

    return true;
}

q_reverse

逐一走訪鏈結串列的節點，將所有節點的 next 及 prev 交換。

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

    struct list_head *now = head;
    do {
        struct list_head *tmp = now->next;
        now->next = now->prev;
        now->prev = tmp;

        now = now->next;
    } while (now != head);
}

q_sort

使用了我比較熟悉的 merge sort 來實作，但其中要去確保節點的 next 及 prev 都是正確的讓程式碼多了很多不優雅的部份。
參考了 @laneser 的方法之後豁然開朗，原來可以在一開始斷開 head 的 prev ，然後直接當成 singly-linked list 來做，最後再重建 prev。

目前這個版本在 make test 的 trace-14-perf 會不通過。

struct list_head *merge_sorted(struct list_head *list1, struct list_head *list2)
{
    if (!list1)
        return list2;
    if (!list2)
        return list1;

    element_t *cmp1 = list_entry(list1, element_t, list);
    element_t *cmp2 = list_entry(list2, element_t, list);
    if (strcmp(cmp1->value, cmp2->value) <= 0) {
        list1->next = merge_sorted(list1->next, list2);
        return list1;
    } else {
        list2->next = merge_sorted(list1, list2->next);
        return list2;
    }
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    return merge_sorted(merge_sort(head), merge_sort(fast));
}

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

    // rebuild prev link
    struct list_head *i = head;
    while (i->next != NULL) {
        i->next->prev = i;
        i = i->next;
    }
    head->prev = i;
    i->next = head;
}

將 merge_sorted 中的遞迴改成疊代後終於通過測試了。

struct list_head *merge_sorted(struct list_head *list1, struct list_head *list2)
{
    struct list_head *result = NULL, *now = result;
    while (true) {
        element_t *cmp1 = list_entry(list1, element_t, list);
        element_t *cmp2 = list_entry(list2, element_t, list);
        if (strcmp(cmp1->value, cmp2->value) <= 0) {
            if (result == NULL) {
                result = list1;
                now = result;
            } else {
                now->next = list1;
                now = now->next;
            }
            list1 = list1->next;
            if (!list1) {
                now->next = list2;
                break;
            }
        } else {
            if (result == NULL) {
                result = list2;
                now = result;
            } else {
                now->next = list2;
                now = now->next;
            }
            list2 = list2->next;
            if (!list2) {
                now->next = list1;
                break;
            }
        }
    }
    return result;
}

在 qtest 提供新的命令 shuffle

在 qtest.c 的 console_init 中加入

ADD_COMMAND(shuffle, "                | Shuffle queue");

並實作 do_shuffle 函式

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    if (!l_meta.l)
        report(3, "Warning: Try to access null queue");
    error_check();

    srand((unsigned int) (time(NULL)));
    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(l_meta.l);
    exception_cancel();

    set_noallocate_mode(false);

    show_queue(3);
    return !error_check();
}

在 queue.h 及 queue.c 中加入 q_shuffle 的定義並實作

void swap_node(struct list_head *node1, struct list_head *node2)
{
    struct list_head *tmp = node1->prev;
    list_move(node1, node2);
    list_move(node2, tmp);
}

struct list_head *list_idx(struct list_head *head, int idx)
{
    do {
        head = head->next;
    } while (idx--);
    return head;
}

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

    int len = q_size(head);
    for (int i = len - 1; i > 0; i--) {
        int idx = rand() % (i + 1);
        swap_node(list_idx(head, idx), list_idx(head, i));
    }
}

結果發現因為修改到了 queue.h ，所以在 git commit 的時候會被擋下來，因此放棄在 queue.c 中實作，改為直接將 q_shuffle 放在 qtest.c 中。