2023q1 Homework1 (lab0)

contributed by < csm1735 >

開發環境

$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  1
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         3500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4999.90

改進 queue.c

q_new

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

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) {
        q_release_element(entry);
    }
    free(l);
}

釋放已配置的記憶體，考量到刪除節點後，還需要找到下一個節點的位置，因此這邊選擇使用 list_for_each_entry_safe 來實作。

q_insert_head / tail

element_t *new_element(char *s)
{
    element_t *element = malloc(sizeof(*element));
    if (!element) {
        free(element);
        return NULL;
    }
    element->value = strdup(s);
    if (!element->value) {
        free(element);
        return NULL;
    }
    return element;
}

實作後發現 q_insert_head 跟 q_insert_tail 在程式碼上有大量重複的狀況，考量到精簡度及維護性，因此選擇將重複部分獨立成 new_element 來使用。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = new_element(s);
    if (!element)
        return false;
    list_add(&element->list, head);
    return true;
}

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *element = new_element(s);
    if (!element)
        return false;
    list_add_tail(&element->list, head);
    return true;
}

q_insert_head 跟 q_insert_tail 主要差異在於一個使用了 list_add 而另一個使用了 list_add_tail 。

q_remove_head

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

一開始沒有看懂說明，以為要對 sp 做 malloc ，所以產生了問題，後來發現應該直接去檢查 sp 是否為 NULL ， 再來做 strncpy 。

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 *tmp = list_last_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&tmp->list);
    return tmp;
}

跟 q_remove_head 主要差異在於其使用了 list_first_entry 而這邊使用了 list_last_entry 。

q_size

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

目前沒有想到其他更有效率的做法，只能透過走訪所有的節點來計算 size 。

q_delete_mid

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    size_t len = q_size(head), count = -1;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        ++count;
        if (count == len / 2) {
            list_del(&entry->list);
            q_release_element(entry);
            break;
        }
    }
    return true;
}

找出中間的節點後，將其移除並釋放記憶體。

q_delete_dup

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    bool flag = 0;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list) {
        if (&safe->list == head) {
            if (flag == 1) {
                list_del(&entry->list);
                q_release_element(entry);
            }
            break;
        }

        if (strcmp(entry->value, safe->value) == 0) {
            list_del(&entry->list);
            q_release_element(entry);
            flag = 1;
        } else if (flag == 1) {
            list_del(&entry->list);
            q_release_element(entry);
            flag = 0;
        }
    }
    return true;
}

這邊函式需要佇列在排序完的狀況下執行，去刪除具有相同字串的節點，假設這邊有

$N$ 個相同字串的節點，那麼前

$N-1$ 個可以透過 strcmp 的判斷來做刪除，第

$N$ 個則是透過 flag 的檢查來做刪除 。

撰寫更精簡的程式碼。

jserv

list_for_each_entry_safe (entry, safe, head, list) {
    if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
        list_del(&entry->list);
        q_release_element(entry);
        flag = 1;
    } else if (flag == 1) {
        list_del(&entry->list);
        q_release_element(entry);
        flag = 0;
    }
}

將 list_for_each_entry_safe 內調整為更精簡的寫法

q_swap

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    q_reverseK(head, 2);
    return;
}

此函式 swap 的實質意義就等同於 q_reverseK 在參數 k 值為 2 的時候。

是否可據此進一步精簡程式碼？

jserv

q_reverse

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) {
        list_move(node, head);
    }
    return;
}

將所有的節點依序搬到頭後就等同於完成 reverse ， 要注意這邊得使用 list_for_each_safe 。

q_reverseK

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;
    struct list_head *node, *safe, *head_from = head, tmp;
    INIT_LIST_HEAD(&tmp);
    size_t count = 0;
    list_for_each_safe (node, safe, head) {
        ++count;
        if (count == k) {
            list_cut_position(&tmp, head_from, node);
            q_reverse(&tmp);
            list_splice_init(&tmp, head_from);
            head_from = safe->prev;
            count = 0;
        }
    }
    return;
}

這邊參考了 komark06 的作法，每 k 個節點就切出來做 reverse 的動作，然後再將其連接回去。

q_sort

不用張貼完整程式碼，你應該闡述自己的想法、考量因素，還有分析已有方案的優缺點，並記錄過程中遇到的問題。

jserv

struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2)
{
    if (!l2)
        return l1;
    if (!l1)
        return l2;

    element_t *n1 = list_entry(l1, element_t, list);
    element_t *n2 = list_entry(l2, element_t, list);

    if (strcmp(n1->value, n2->value) < 0) {
        l1->next = mergeTwoList(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoList(l1, l2->next);
        return l2;
    }
}

mergeTwoList 原先的遞迴寫法，雖然程式碼較為精簡，但在 make test 時效能上無法通過，因此修正為以下的迴圈版本

struct list_head *mergeTwoList(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head, *tmp;
    element_t *n1 = list_entry(l1, element_t, list);
    element_t *n2 = list_entry(l2, element_t, list);
    if (strcmp(n1->value, n2->value) < 0) {
        tmp = l1;
        l1 = l1->next;
    } else {
        tmp = l2;
        l2 = l2->next;
    }
    head = tmp;
    
    while(l1 && l2) {
        n1 = list_entry(l1, element_t, list);
        n2 = list_entry(l2, element_t, list);
        if(strcmp(n1->value, n2->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;

}

struct list_head *mergeSortList(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 = mergeSortList(head);
    struct list_head *l2 = mergeSortList(fast);

    // merge sorted l1 and sorted l2
    return mergeTwoList(l1, l2);
}

以上 merge sort 實作參考自 Linked List Sort

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

    struct list_head *cur;
    for (cur = head; cur->next; cur = cur->next)
        cur->next->prev = cur;
    cur->next = head;
    head->prev = cur;
    return;
}

透過 merge sort 來完成排序，在實作時一開始忘記將最後一個節點的 next 指向 NULL ，導致程式有無窮迴圈的問題，需要注意，另外在排序完後，記得要將每個節點的 prev 重新連結上，還有將最後一個節點的 next 重新指向 head ，這樣才算完成。

q_descend

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

    element_t *maxNode = list_last_entry(head, element_t, list),
              *curNode = NULL;
    int count = 0;
    for (struct list_head *cur = head->prev, *safe = cur->prev; cur != head;
         cur = safe, safe = cur->prev) {
        curNode = list_entry(cur, element_t, list);
        if (strcmp(maxNode->value, curNode->value) > 0) {  
            list_del(&curNode->list);
            q_release_element(curNode);
        } else {
            maxNode = curNode;
            ++count;
        }
    }

    return count;
}

這邊的做法是從後往前掃來做檢查， maxNode 即為當前節點右側的節點中擁有最大值的那一個，當前節點的值如果小於 maxNode 的值則做刪除的動作，反之則更新成 maxNode 。

q_merge

int q_merge(struct list_head *head)
{
    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain),
                   *entry = NULL;
    list_for_each_entry (entry, head, chain) {
        if (entry->id == first->id) {
            continue;
        }
        list_splice_init(entry->q, first->q);
    }
    q_sort(first->q);
    return q_size(first->q);
}

這邊很直接的先將所有的佇列連接在一起，然後再一口氣一次將全部做排序，但這邊並沒有運用到各個佇列已經排序好的性質，可以再思考更好的做法。

避免不精準的詞彙，「一口氣」對應的英語是什麼？這對於解析程式有何幫助？

jserv

已修正，謝謝老師

目前測試分數 95 / 100
複雜度仍須提升

---

以 Valgrind 分析記憶體問題

用 make valgrind 來測試，發現大部分都有如下的狀況:

==32347== 32 bytes in 1 blocks are still reachable in loss record 1 of 6
==32347==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==32347==    by 0x10CBE0: do_new (qtest.c:146)
==32347==    by 0x10DF3F: interpret_cmda (console.c:181)
==32347==    by 0x10E4F4: interpret_cmd (console.c:201)
==32347==    by 0x10E8F5: cmd_select (console.c:610)
==32347==    by 0x10F1E1: run_console (console.c:705)
==32347==    by 0x10D331: main (qtest.c:1274)

後來發現在 qtest.c 中的 q_quit 裡面，第一行就直接做了 return true; ，因此趕快將這行拿掉就恢復正常了，而後來發現這個問題在原本的 lab0 已經被修正掉了，這也提醒了我要記得同步專案。

測試結果 100 / 100

---

在 qtest 提供新的命令 shuffle

實作 shuffle

一開始花了一些時間摸索如何在 qtest 中提供新的命令，後來發現要在 qtest.c 中的 console_init 加入以下程式碼。

ADD_COMMAND(shuffle, "Shuffle queue", "");

並在 qtest.c 中新增 do_shuffle 函式來實作洗牌功能。

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

    if (!current) {
        report(3, "Warning: Try to operate null queue");
        return false;
    }

    set_noallocate_mode(true);
    if (exception_setup(true))
        q_shuffle(current->q);
    exception_cancel();

    set_noallocate_mode(false);

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

以下 q_shuffle 則是基於 Fisher–Yates shuffle 演算法的 Modern method 來實作。

void q_shuffle(struct list_head *head)
{
    int len = q_size(head), roll = 0;
    struct list_head *rollNode = head->next, *lastNode = head->prev;
    for (int i = len; i > 1; --i) {
        roll = rand() % i;
        if (roll == i - 1) {
            lastNode = lastNode->prev;
            continue;
        }
        rollNode = head->next;
        for (int j = 0; j < roll; ++j)
            rollNode = rollNode->next;
        // swap value
        element_t *A = list_entry(rollNode, element_t, list),
                  *B = list_entry(lastNode, element_t, list);
        char *tmp = A->value;
        A->value = B->value;
        B->value = tmp;

        lastNode = lastNode->prev;
    }
    return;
}

如果隨機抽選到的 node 是尚未被選擇的最後一個 node (也就是將被交換的那一個)，則省略交換的過程，直接做 continue ，反之則針對值來做交換的動作。

亂度分析

有待分析

執行 option entropy 1

cmd> option entropy 1
cmd> ih RAND 10
l = [jmhfj(21.88%) dlubbo(26.56%) abzjqxrsr(35.94%) uuiye(21.88%) 
mxfangfme(32.81%) rdjtz(26.56%) dpjujvuf(29.69%) yvrkshlka(35.94%) 
dkgjszx(32.81%) xgvygicw(32.81%)]