2022q1 Homework1 (lab0)

contributed by < Wallmountain >

實驗環境

$ 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-8750H CPU @ 2.20GHz
Stepping:                        10
CPU MHz:                         1637.560
CPU max MHz:                     4100.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4399.99
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-11

作業要求

閱讀 lab0 說明，依據指示著手修改 queue.[ch] 和連帶的檔案，測試後用 Git 管理各項修改，並利用 Cppcheck 和 Valgrind 作程式評估。

• 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: 移走佇列中間的節點
• q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
• q_swap: 交換佇列中鄰近的節點
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
• q_sort: 以遞增順序來排序鏈結串列的節點

開發過程

q_new

建立空佇列，檢查 malloc 是否正常運作

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

q_free

釋放所有佇列所佔記憶體

void q_free(struct list_head *l)
{
    if (!l) {
        return;
    }
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, l, list) {
        list_del_init(&entry->list);
        q_release_element(entry);
    }
    free(l);
}

q_insert_head

檢查 malloc 有沒有給指定大小的記憶體，字串結尾要加 '\0'

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;
    }
    int length = strlen(s);
    node->value = (char *) malloc(length + 1);
    if (!node->value) {
        q_release_element(node);
        return false;
    }
    for (int i = 0; i < length; i++) {
        node->value[i] = s[i];
    }
    node->value[length] = '\0';
    list_add(&node->list, head);
    return true;
}

q_insert_tail

跟 insert head 基本相同

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head) {
        return false;
    }
    element_t *node = (element_t *) malloc(sizeof(element_t));
    if (!node) {
        return false;
    }
    int length = strlen(s);
    node->value = (char *) malloc(length + 1);
    if (!node->value) {
        q_release_element(node);
        return false;
    }
    for (int i = 0; i < length; i++) {
        node->value[i] = s[i];
    }
    node->value[length] = '\0';
    list_add_tail(&node->list, head);
    return true;
}

q_size

計算目前佇列的節點總量

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

q_delete_mid

移走佇列中間的節點, 使用前面的 q_size 得到佇列長度

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return false;
    }
    struct list_head *node = head->next;
    int size = q_size(head) / 2;

    while (size--) {
        node = node->next;
    }

    list_del_init(node);
    q_release_element(list_entry(node, element_t, list));
    return true;
}

q_delete_dup

刪除值重複的 node

bool q_delete_dup(struct list_head *head)
{
    if (!head) {
        return false;
    }
    struct list_head *node = head->next;
    while (node->next != head) {
        element_t *tmp = list_entry(node->next, element_t, list);
        if (strcmp(list_entry(node, element_t, list)->value, tmp->value) == 0) {
            list_del_init(node->next);
            q_release_element(tmp);
        } else {
            node = node->next;
        }
    }
    return true;
}

q_swap

交換佇列中鄰近的節點，不用額外指標便可 swap

void q_swap(struct list_head *head)
{
    if (!head) {
        return;
    }
    struct list_head *node = head->next;
    while (node->next != head) {
        // swap
        node->next->prev = node->prev;
        node->prev->next = node->next;
        node->next->next->prev = node;
        node->prev = node->next;
        node->next = node->next->next;
        node->prev->next = node;

        node = node->next;
    }
}

q_reverse

以反向順序重新排列鏈結串列, trace 過整個佇列一個一個把他們的 prev 和 next 交換

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return;
    }
    struct list_head *tmp = head->next;
    head->next = head->prev;
    head->prev = tmp;
    struct list_head *node;
    list_for_each (node, head) {
        tmp = node->next;
        node->next = node->prev;
        node->prev = tmp;
    }
}

q_sort

一開始，下意識以為就是要作 quicksort, 然後打完才發現， 而且 quicksort 的 worst case 為

$O(n^2)$,故下面就繼續實作老師上課提到的 mergesort

quicksort

void q_sort(struct list_head *head)
{
    if (!head || head->next == head->prev) {
        return;
    }
    struct list_head *left, *right, *pivot;
    left = q_new();
    right = q_new();

    pivot = head->next;
    list_del(pivot);

    // partition
    while (!list_empty(head)) {
        struct list_head *tmp, *t_head;
        tmp = head->next;
        list_del(tmp);
        t_head = (strcmp(list_entry(pivot, element_t, list)->value,
                         list_entry(tmp, element_t, list)->value) < 0)
                     ? right
                     : left;

        list_add_tail(tmp, t_head);
    }

    q_sort(left);
    q_sort(right);

    list_add_tail(pivot, left);
    list_splice_tail(right, left);
    q_release_element(list_entry(right, element_t, list));
}

mergesort

參照 jserv 的實作，在 mergesort 當中當作queue為單向的

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

    for (; left && right; *node = (*node)->next) {
        node = (strcmp(list_entry(left, element_t, list)->value,
                       list_entry(right, element_t, list)->value) < 0)
                   ? &left
                   : &right;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *) ((uintptr_t) left | (uintptr_t) right);
    return head;
}

struct list_head *mergesort_list(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }

    struct list_head *slow = head, *right;
    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next)
        slow = slow->next;

    right = slow->next;
    slow->next = NULL;

    head = mergesort_list(head);
    right = mergesort_list(right);
    return mergetwoqueues(head, right);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *node = head->next;
    head->prev->next = NULL;
    node = mergesort_list(node);

    head->next = node;
    for (node = head; node->next; node = node->next) {
        node->next->prev = node;
    }
    node->next = head;
    head->prev = node;
}

提供新的命令 shuffle

觀察如何加入新命令， 找到 ADD_COMMAND 巨集的定義

#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)

將 shuffle 加入命令

ADD_COMMAND(shuffle, "| Fisher-Yates shuffle algorithm");

模仿 do_sort 實作 do_shuffle

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: Calling sort on null queue");
    error_check();

    int cnt = q_size(l_meta.l);
    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

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

q_shuffle

依據 Fisher–Yates shuffle 作出的函式，隨機選出node搬到最後，每次都減少能選取範圍，直到node都已經被選取過

void q_shuffle(struct list_head *head)
{
    int len = q_size(head);
    if (len < 2)
        return;

    for (; len > 1; len--) {
        int n = rand() % len;

        struct list_head *cur = head->next;
        for (; n; n--) {
            cur = cur->next;
        }
        list_del(cur);
        list_add_tail(cur, head);
    }
}

參考資料

• laneser