2024q1 Homework1 (lab0)

contributed by < otteryc >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            9
    CPU max MHz:         4500.0000
    CPU min MHz:         800.0000
    BogoMIPS:            8400.00

針對佇列操作的程式碼實作

q_insert_head

依 queue.h 檔案中之指示，本函式當明確地分配 配置空間，並將傳入字串 s 存入所新增於佇列的物件中。

allocate 翻譯為「配置」，而非「分配」，這樣才可跟 dispatch 的翻譯區隔，二者都頻繁在作業系統領域出現。

惟查，關於 s 字串之大小，作業說明以及程式碼中，並無明確說明。為妥適配置記憶體，減少程式開銷，吾人查詢呼叫 q_insert_head 以及 q_insert_tail 之程式碼區段：

改進你的漢語表達，文言文擬古不能掩蓋行文不流暢的現象，以清晰且無語病的白話文書寫。

巨集 dut_insert_head ，所插入的字串係由 get_random_string 產生，而 random_string 則是由 prepare_inputs產生，揆諸前開函式，可知 random_string 長度固定為 8 個字元，而且是 well null-terminated。

static char random_string[N_MEASURES][8];
static char *get_random_string(void)
{
    random_string_iter = (random_string_iter + 1) % N_MEASURES;
    return random_string[random_string_iter];
}

void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
    randombytes(input_data, N_MEASURES * CHUNK_SIZE);
    for (size_t i = 0; i < N_MEASURES; i++) {
        classes[i] = randombit();
        if (classes[i] == 0)
            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
    }

    for (size_t i = 0; i < N_MEASURES; ++i) {
        /* Generate random string */
        randombytes((uint8_t *) random_string[i], 7);
        random_string[i][7] = 0;
    }
}

次查，在 linenoice.c 中，規定 console 中每行指令之上限為 4096

#define LINENOISE_MAX_LINE 4096

減少非必要的項目縮排 (即 * )，使用清晰、明確，且流暢的漢語書寫。

本於上述觀察，吾人獲悉佇列中單一元素（即 element_t）中所指向的字串，大小最多為 4096 個位元。嘗試將之作為單一元素所指向的字串的長度上限，惟此舉會導致 make test 時，超過記憶體限制，只能以實作上需要兩次遍歷 走訪的 strdup(3) 替代之。

留意資訊科技詞彙翻譯

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head || !s)
        return false;
    element_t *n = malloc(sizeof(element_t));
    if (!n)
        return false;
-   n->value = malloc(MAX_STRING_LEN);
+   n->value = strdup(s);
    if (!n->value) {
        free(n);
        return false;
    }
-   strncpy(n->value, s, MAX_STRING_LEN);
    list_add(&n->list, head);
    return true;
}

q_insert_tail

本函式與 q_insert_head 的實作幾近相同，差異者係在插入新物件時，所使用之函式應改為 list_add_tail ，僅此而已。
TODO: 兩函式的實作或許可改以 macro 實作 ，俾降低程式碼維護成本。

「或許」不該簡稱為「或」，否則會造成歧義。

q_reverse

依題旨，本題 本函式不得涉及記憶體管理的操作，本函式的想法是用兩個指標，fast 指標儲存被操作的物件的下一個物件的記憶體位置，slow 指標則負責將 list_head 結構體中分別指往前後的指標反向。並且，當 slow 指向 head 時，就代表反向完成。

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *fast = head->next, *slow = head, *tmp;
    do {
        tmp = slow->next;
        slow->next = slow->prev;
        slow->prev = tmp;
    } while (slow = fast, fast = fast->next, slow != head);
}

q_delete_mid

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

本題由於這份作業的 queue 是由 doubly circular linked-list 實作，除了針對 singly linked-list 的快慢指標來尋找在佇列正中央的節點以外，還可以透過兩個指標分別從 head 跟 tail 開始互為反向地走訪，當兩個指標相遇時，就是佇列中點，並刪除之。

struct list_head *right = head->next, *left = head->prev;
while (true) {
    if (right == left) 
        break;
    right = right->next;
    if (right == left)
        break;
    left = left->prev;
}

上述程式碼，值得注意的是，讓 right 提早 left 移動一步，如此就可以解決當佇列中元素個數為偶數的情形，像是下圖情形，應被從佇列中刪除的是標示為 2 號的元素。

不該言及「本題」，個別函式之間存在關聯，應看待為整體的創作，只是依據工程開發的角度，逐項分析和探討。

q_sort

這一個函式依照指示用 merge sort 完成，在進行 conquer 的時候所用的函式可以獨立出來，供 q_merge 函式呼叫。

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_is_singular(head) || list_empty(head))
        return;

    struct list_head *right = head->next, *left = head->prev;
    while (true) {
        if (right == left)
            break;
        left = left->prev;
        if (right == left)
            break;
        right = right->next;
    }

    LIST_HEAD(mid);
    list_cut_position(&mid, head, right);

    q_sort(head, descend);
    q_sort(&mid, descend);

    merge_sort_conquer(head, &mid, descend);
}

這裡一樣要尋找佇列中點，不過應該注意的是，當佇列內的節點個數是偶數時，應該要取的節點與上一個函式不同。

在這個情況下，應該要取編號為 0 的節點作為中點進行分出兩個子佇列，否則將無法有效的分治。

static void merge_sort_conquer(struct list_head *dest,
                               struct list_head *victim,
                               bool descend)
{
    int mask = descend ? 0 : INT_MIN;
    LIST_HEAD(result);
    struct list_head *insert;
    while (!list_empty(dest) && !list_empty(victim)) {
        element_t *e_victim = list_first_entry(victim, element_t, list),
                  *e_dest = list_first_entry(dest, element_t, list);
        insert = strcmp(e_victim->value, e_dest->value) & mask ? victim->next
                                                               : dest->next;
        list_move_tail(insert, &result);
    }

    insert = list_empty(dest) ? victim : dest;
-   list_splice_tail(insert, &result);
+   list_splice_tail_init(insert, &result)

    list_splice(&result, dest);
    return;
}

另外，在 conquer 的部分，透過 strcmp 函式回傳的值來判斷兩個節點之間的大小，根據 man strcmp(3)：

strcmp() returns an integer indicating the result of the comparison, as follows:
• 0, if the s1 and s2 are equal;
• a negative value if s1 is less than s2;
• a positive value if s1 is greater than s2.

此外，在排序時，兩個節點的內容相等時，孰先孰後並不重要。所以，在判斷要依升冪還是降冪排列時，只要觀查 strcmp 回傳值的 sign bit 就好，可以有效降低進行分支的次數。
另外， list_splice_tail 在搬離所有節點之後，不會妥善的處理來源佇列的 head ，如果這時候再去存取來源佇列的 head ，會造成未定義的結果，所以應該改用 list_splice_tail

q_merge

這個函式所要處理的是把多個以排序佇列合而為一，僅需一一走訪，並使用前述 merge sort 的 conquer 函式把每個佇列連接在一起即可。

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head))
        return 0;
    LIST_HEAD(result);
    queue_contex_t *iter;
    list_for_each_entry (iter, head, chain) {
        // cppcheck-suppress uninitvar
        merge_sort_conquer(&result, iter->q, descend);
        INIT_LIST_HEAD(iter->q);
    }

    list_splice(&result, list_first_entry(head, queue_contex_t, chain)->q);
    return q_size(list_first_entry(head, queue_contex_t, chain)->q);
}

另外，在第 9 行處， cppcheck 似乎會將 iter->q 認為未初始化的變數，由於在 list_for_each_entry 巨集的定義中，有確實的初始化 iter 變數，所以透過 suppress 選項 指令 使 cppcheck 暫不檢查此類潛在錯誤。