2022q1 Homework1 (lab0)

contributed by < vacantron >

實作進度

命令列：

shuffle: 藉由 Fisher–Yates shuffle 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作
web: 提供 web 伺服器功能。注意: web 伺服器運作過程中，qtest 仍可接受其他命令

實驗環境

$ 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
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:                           96
Model name:                      AMD Ryzen 7 4800H with Radeon Graphics
Stepping:                        1
Frequency boost:                 enabled
CPU MHz:                         1400.000
CPU max MHz:                     2900.0000
CPU min MHz:                     1400.0000
BogoMIPS:                        5788.90
Virtualization:                  AMD-V
L1d cache:                       256 KiB
L1i cache:                       256 KiB
L2 cache:                        4 MiB
L3 cache:                        8 MiB
NUMA node0 CPU(s):               0-15

開發過程

q_new

struct list_head *q_new()
{
    struct list_head *node = malloc(sizeof(struct list_head));
    if (!node)
        return NULL;

    INIT_LIST_HEAD(node);
    return node;
}

q_free

使用 container_of 巨集從結構體的成員指標中獲取該結構體的指標

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

    while (!list_empty(l)) {
        struct list_head *curr = l->next;
        list_del(curr);
        q_release_element(container_of(curr, element_t, list));
    }
    list_del(l);
    free(l);
}

q_insert_head

最初使用 strcpy() 函式複製字串，但是在向 git 提交時顯示 dangerous function 提醒，查閱所提供的 Common vulnerabilities guide for C programmers 後，發現如果目的地的空間不足可能會覆寫到非預期的記憶體地址，進而導致錯誤

何謂「被貼上」？理工人說話要精準
jserv

已改善用詞

之後改用 strncpy() 函式，但需要指定要複製的字串長度。因為 C 語言需要一個 \0 字元作為字串的結尾，故在計算字元數時需要特別注意。另外因為 strlen() 函式所回傳的字串長度並不包含中止字元，故在分配記憶體空間時額外增加一個 byte

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

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

    size_t buf = strlen(s) + 1;
    el->value = malloc(buf);
    if (!el->value) {
        free(el);
        return false;
    }

    strncpy(el->value, s, buf);
    list_add(&el->list, head);
    return true;
}

q_insert_tail

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

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

    size_t buf = strlen(s) + 1;
    el->value = malloc(buf);
    if (!el->value) {
        free(el);
        return false;
    }

    strncpy(el->value, s, buf);
    list_add_tail(&el->list, head);
    return true;
}

q_remove_head

因為有限制回傳字串的長度，故需要切割原本的字串，並在尾端加上中止字元

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

    struct list_head *curr = head->next;
    list_del_init(curr);
    element_t *el = list_entry(curr, element_t, list);
    if (sp) {
        strncpy(sp, el->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    return el;
}

q_release_element

void q_release_element(element_t *e)
{
    free(e->value);
    free(e);
}

q_size

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    int cnt = 0;
    struct list_head *curr = head->next;
    while (curr != head) {
        ++cnt;
        curr = curr->next;
    }
    return cnt;
}

q_delete_mid

使用右移運算子取代原本除以 2 並無條件捨去的操作

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return NULL;

    int n = q_size(head) >> 1;
    struct list_head *curr = head->next;
    for (size_t i = 0; i < n; i++) {
        curr = curr->next;
    }
    list_del(curr);
    q_release_element(list_entry(curr, element_t, list));
    return true;
}

q_delete_dup

誤會題意，以為是要刪除有重複字元的節點，應該是要刪除擁有相同字串的節點才對

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *s = list_entry(head->next, element_t, list);
    element_t *t = list_entry(head->next->next, element_t, list);
    while (&t->list != head) {
        size_t len = strlen(s->value) > strlen(t->value) ? strlen(t->value)
                                                         : strlen(s->value);
        if (strncmp(s->value, t->value, ++len) == 0) {
            element_t *next = list_entry(t->list.next, element_t, list);
            list_del(&t->list);
            q_release_element(t);
            t = next;
        } else {
            s = t;
            t = list_entry(t->list.next, element_t, list);
        }
    }
    return true;
}

q_swap

紀錄

更正無法處理奇數節點的錯誤

void q_swap(struct list_head *head)
{
    int n = q_size(head) >> 1;
    bool is_odd = q_size(head) % 2;
    struct list_head *prev = head, *curr = head->next;
    for (size_t i = 0; i < n; i++) {
        struct list_head *next = curr->next, *tmp;
        prev->next = next;
        tmp = next->next;
        next->prev = prev;
        next->next = curr;
        curr->prev = next;
        prev = curr;
        curr = tmp;
    }
    if (is_odd) {
        prev->next = head->prev;
        head->prev->prev = prev;
    } else {
        prev->next = head;
        head->prev = prev;
    }
}

改用 Linux kernel API 的更簡潔的實作

void q_swap(struct list_head *head)
{
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        if (node->next == head)
            continue;
        list_del(node);
        list_add(node, safe);
        safe = node->next;
    }
}

q_reverse

紀錄

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

    struct list_head *curr = head, *tmp = head->next;
    while (tmp != head) {
        struct list_head *next = tmp;
        curr->prev = next;
        tmp = next->next;
        next->next = curr;
        curr = next;
    }
    curr->prev = head;
    head->next = curr;
}

使用 Linux kernel API 簡化

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

    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        node->next = node->prev;
        node->prev = safe;
    }
    node = head->prev;
    head->prev = head->next;
    head->next = node;
}

q_sort

bubble sort 紀錄

void swap(element_t *, element_t *);
void q_sort(struct list_head *head)
{
    if (!head)
        return;
    if (list_empty(head))
        return;

    bool is_swapped = false;
    int displacement = q_size(head) - 1;
    do {
        is_swapped = false;
        element_t *s = list_entry(head->next, element_t, list);
        element_t *t = list_entry(head->next->next, element_t, list);

        for (size_t i = 0; i < displacement; i++) {
            size_t len = strlen(s->value) > strlen(t->value) ? strlen(t->value)
                                                             : strlen(s->value);
            if (strncmp(s->value, t->value, ++len) > 0) {
                swap(s, t);
                is_swapped = true;
            }
            s = t;
            t = list_entry((&s->list)->next, element_t, list);
        }
        if (!is_swapped)
            --displacement;
    } while (is_swapped);
}

void swap(element_t *s, element_t *t)
{
    struct list_head *prev = (&s->list)->prev;
    struct list_head *next = (&t->list)->next;
    (&s->list)->prev = &t->list;
    (&s->list)->next = next;
    (&t->list)->prev = prev;
    (&t->list)->next = &s->list;

    prev->next = &t->list;
    next->prev = &s->list;
}

使用遞迴式實作 merge sort

使用 circular-doubly-linked list 能更方便的找到頭尾而不必再走訪整個鏈結串列，但被限制無法在 q_sort 內配置額外的記憶體，故改變原本的鏈結串列結構，將 head 指標暫時從串列中移除

因為以上的操作造成部份 API 無法使用，故新增函式方便操作

int pseudo_size(struct list_head *pseudo_head)
{
    int cnt = 1;
    struct list_head *curr = pseudo_head->next;
    while (curr != pseudo_head) {
        ++cnt;
        curr = curr->next;
    }
    return cnt;
}

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

    list_del(head);
    struct list_head *pseudo_head = merge_sort(head->next);
    pseudo_head->prev->next = head;
    head->prev = pseudo_head->prev;
    pseudo_head->prev = head;
    head->next = pseudo_head;
}

struct list_head *merge_sort(struct list_head *head)
{
    size_t len = pseudo_size(head);
    if (len == 1)
        return head;

    len = len >> 1;
    struct list_head *lhs = head, *rhs = head;
    for (size_t i = 0; i < len; i++) {
        rhs = rhs->next;
    }

    struct list_head *tail = head->prev;
    lhs->prev = rhs->prev;
    lhs->prev->next = lhs;
    rhs->prev = tail;
    rhs->prev->next = rhs;

    return merge(merge_sort(lhs), merge_sort(rhs));
}

struct list_head *merge(struct list_head *l, struct list_head *r)
{
    struct list_head *iterator = l, *curr = r;
    for (; iterator; curr = curr->next) {
        char *l_char = list_entry(l, element_t, list)->value;
        char *curr_char = list_entry(curr, element_t, list)->value;
        size_t len = strlen(l_char) > strlen(curr_char) ? strlen(curr_char)
                                                        : strlen(l_char);
        if (strncmp(l_char, curr_char, ++len) <= 0) {
            l->next->prev = l->prev;
            l->prev->next = l->next;
            iterator = l->next;
            if (iterator == l)
                iterator = NULL;

            curr->prev->next = l;
            l->prev = curr->prev;
            curr->prev = l;
            l->next = curr;

            if (curr == r)
                r = l;

            curr = curr->prev;
            l = iterator;
        } else if (curr == r->prev) {
            struct list_head *tail = iterator->prev;
            iterator->prev = r->prev;
            r->prev->next = iterator;
            r->prev = tail;
            tail->next = r;
            return r;
        }
    }
    return r;
}

命令列

shuffle

修改 qtest.c 檔案，新增 shuffle 命命










static void console_init()
{
    ......
        
+   ADD_COMMAND(shuffle,
+               "                | Shuffle all queue elements with "
+               "Fisher-Yates shuffle algorithm");
    
    ......
}

新增 do_suffle 函式。其中可以藉由 argc 檢查是否有輸入多餘的參數

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

    size_t len = q_size(head), idx = 0;
    for (size_t i = 0; i < len - 1; i++, idx++) {
        long location = random() % (len - idx);
        struct list_head *node = head->next;
        for (size_t j = 0; j < location; j++) {
            node = node->next;
        }
        list_del(node);
        list_add_tail(node, head);
    }
}

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

    if (exception_setup(true))
        q_shuffle(l_meta.l);

    exception_cancel();

    show_queue(3);

    return !error_check();
}