2025q1 Homework1 (lab0)

contributed by < WavJaby >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 14.2.0-4ubuntu2) 14.2.0
Copyright (C) 2024 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):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700KF
    CPU family:           6
    Model:                151
    Thread(s) per core:   1
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             2
    BogoMIPS:             7219.20
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_kn
                          own_freq pni pclmulqdq ssse3 cx16 sse4_1 sse4_2 movbe popcnt aes rdrand hypervisor lahf_lm abm 3dnowprefetch ibrs_enhanced fsgsbase bmi1 bmi2 invpcid rdseed adx clflushopt sha_ni arat
                           md_clear flush_l1d arch_capabilities

/**
 * 以前只有寫過小專案，或是找好玩的小專案貢獻一下，
 * 所以沒有寫過這麼正式的開發日誌或是commit，
 * 希望我可以趁這個機會好好練習一下
 * @param homework lab0
 * @param date 2025/03/XX
 * @return queue.c
 */

實作 `queue.c`

首先學習如何撰寫一個好的 commit message，我認為比較重要的是限制標題最多只有 50 字元，之前都不知道有這個規則，只知道以祈使句撰寫標題。

接著進行牛刀小試環節，並產生第一個 commit 85e9348。因為沒有使用過 Git hook 所以不知道 Change-Id 什麼時候會生成出來，怎麼生成出來。

俗話說得好

Software and cathedrals are much the same – first we build them, then we pray.
-Sam Redwine

秉持著這個心情，按下 Enter 之後，Change-Id 成功的出現在我的 commit message 裡面。

終於可以開始寫程式了╰(*°▽°*)╯ 這個不算emoji。

Implement `q_new`, `q_free` functions 6b7a573

我在寫

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

的時候習慣把 new 和 free 一起寫，因為需要 new 的地方就會需要 free ，不然到時候寫一寫忘記這東西到底怎麼 new 的，就又要回去看code，很累。

像是之前我寫了一個自己的 string 函式庫 wjcl_string.h ，原因是因為平常取得字串長度都用 strlen ，每次都要遍歷字串的所有字元，感覺就慢得要死。
所以我想到一個在確保字串可以正常使用的前提下(例如可以直接丟到 printf 裡面)，儲存長度的方法，就是在創建字串時，多創建 8 byte 來存字串長度，然後回傳 ptr + 8 把那 8 byte 藏在字串的前面，需要 free 的時候再 ptr - 8 就好了。

缺點就是不能用內建的 strcat 之類的功能，長度就會跑掉，~~但這個就比較好用，我才不用內建的~~。

q_new 的部分，在 malloc 完後，先確認有沒有成功，然後使用 INIT_LIST_HEAD 初始化 list head。
q_free 的部分，使用 list_for_each_entry_safe 來遍歷整個鏈結串列，並使用 q_release_element 來釋放鏈結串列中的所有元素。

這邊不能使用 list_for_each_entry 是因為如果當前的元素已經釋放掉後，就無法取得下一個元素了，使用 list_for_each_entry_safe 會預先取得下一個元素，在下一輪迴圈時直接變更為當前元素，然後在預先取得下一個元素，這樣就避免了這個問題。

Implement `q_insert_head`, `q_insert_tail` functions cfb2fae

我同時實作了這兩個函式，因為他們都有一個相似處，就是要創建一個新的 element_t 並加入到鏈結串列中。
所以我另外實作了一個函式 create_element 來創建新的元素。

static inline element_t *create_element(char *s)
{
    element_t *element = malloc(sizeof(element_t));
    if (!element)
        return NULL;
    element->value = strdup(s);
    // If string copy failed, free the element
    if (!element->value) {
        free(element);
        return NULL;
    }
    return element;
}

首先先確認 element_t 有沒有創建成功，接著複製字串。
這邊使用 harness.h 標頭檔中的 strdup 來複製字串，方便之後追蹤記憶體配置和釋放的狀況
如果字串複製失敗，要釋放剛剛創建好的 element_t 並回傳 NULL

接著只要呼叫 create_element 並且判斷有沒有創建成功後，

q_insert_head 使用 list_add(&entry->list) 將節點插入頭
q_insert_tail 使用 list_add_tail(&entry->list) 將節點插入尾

Implement q_remove_head, q_remove_tail c24fe3d

這兩個函式也有共通處，但我有點懶惰就沒有把他們拆出去了，主要差別在於一個使用 list_first_entry 另一個是 list_last_entry。
首先兩個函式都要先判斷鏈結串列中有沒有東西，如果是空的就直接跳出

if (!head || list_empty(head))
     return NULL;

接下來取得 element_t ，

q_remove_head 使用 list_first_entry 取得鏈結串列中第一個元素
q_remove_tail 使用 list_last_entry 取得鏈結串列中最後一個元素

queue.h 標頭檔中有註明 If sp is non-NULL and an element is removed, copy the removed string to *sp (up to a maximum of bufsize-1 characters, plus a null terminator.)
意思是如果有成功移除元素而且 sp != NULL ，要複製元素中的字串到 sp ，並且最大長度是 bufsize - 1，所以我使用 strncpy 複製字串，然後在大長度加上 null terminator。

if (sp && bufsize) {
    strncpy(sp, entry->value, bufsize - 1);
    sp[bufsize - 1] = '\0';
}

最後把這個元素從鏈結串列中移除，而且是"移除"，不是"刪除"，所以我使用 list_del_init ，僅將元素從鏈結串列移除，並且初始化元素中的 list_head ，最後回傳被移除的元素。

Implement q_delete_mid 60e0295

因為之後會實作 merge sort 也會需要找中間值，所以我建立了一個新的函式 _q_find_mid ，我是用左右一起往中間夾的方式找中間的節點，

static inline struct list_head *_q_find_mid(struct list_head *left,
                                             struct list_head *right)
{
    while (left != right) {
        left = left->next;
        // When there are an even number of nodes, select next first
        if (right == left)
            break;
        right = right->prev;
    }
    return left;
}

如果是鏈結串列長度是偶數，優先去得靠左邊的節點，所以如果 left->next == right 的時候，就可以直接跳出迴圈。

有了這個函式後，在 q_delete_mid 中就可以呼叫這個函式拿到中間的節點，

struct list_head *mid = _q_find_mid(head->next, head->prev);
list_del(mid);
q_release_element(list_entry(mid, element_t, list));

然後用 list_del 先將節點從鏈結串列中移除，然後用 q_release_element 釋放元素。

Implement q_reverse 259dfbc

如果想要把整個鏈結串列反過來的話，只要遍歷每個節點，然後一個一個插入到鏈結串列的最前面就可以了，所以我用 list_for_each_safe (node, safe, head) 來取得每一個節點，然後用 list_move(node, head) 把每個節點都移到最前面。

Implement q_swap ed44ff8

這個函式要把每兩個節點一組然後交換，一樣使用 list_for_each_safe (node, next, head) 取得兩個節點，然後用 list_move(node, next) 把 node 挪到 next 的下一個。
然後在挪動之前要先確保 next != head ，因為如果鏈結串列長度是奇數的話，最後一組的 next 會等於 head。
最後因為我們把 node 移到 next 後面了，所以我把 next = node->next 讓下個迴圈的 node 變成下一組。

Implement q_ascend and q_descend cabf09a

這兩個函式也是有共通點，所以我建立了一個函式 _q_remove_not_in_order 來找不符合順序的節點並且刪除它們。
因為要判斷兩個元素的順序(升序或降序)，所以我建立了一個函式 _q_value_cmpare ，來判斷兩個字串是否符合規則

static inline int _q_value_cmpare(char *a, char *b, bool descend)
{
    return descend ? strcmp(b, a) : strcmp(a, b);
}

接著實作_q_remove_not_in_order 這個函式會遍歷整個鏈結串列，並從每個元素開始，向前檢查前面的元素順序是否正確，如果發現有元素不符合指定的順序，就將其刪除。

list_for_each_entry (curr, head, list) {
    // 從last往前判斷順序
    while (&last->list != head &&
           // 判斷當前以及前面的元素順序
           _q_value_cmpare(curr->value, last->value, descend) < 0) {
        tmp = element_prev(last, list);
        // 刪除不符合順序的元素
        list_del(&last->list);
        q_release_element(last);
        // 往前一個元素
        last = tmp;
    }
    // 紀錄最後一個元素，以供下次判斷
    last = curr;
}

接著在在 q_ascend 以及 q_descend 中，判斷如果鏈結串列大小 <= 1 就直接回傳，否則就要使用 _q_remove_not_in_order 來移除不符合順序的元素

q_ascend 使用 _q_remove_not_in_order(head, false)
q_descend 使用 _q_remove_not_in_order(head, true)

最後再使用 q_size(head) 回傳鏈結串列長度

Implement q_delete_dup fffd619

因為牽涉到移除元素，所以需要使用 list_for_each_entry_safe

if (&next->list != head && strcmp(curr->value, next->value) == 0) {
    list_del(&curr->list);
    q_release_element(curr);
    dup = true;
}

先判斷 curr 是不是跟 next 一樣，如果一樣的話就刪除當前的元素，然後因為要移除所有有重複的元素，所以我用一個布林值 dup 紀錄有找到重複的值

else if (dup) {
    list_del(&curr->list);
    q_release_element(curr);
    dup = false;
}

最後重複直到找到不一樣的值，並且 dup 是 true 的話，也要刪除當前元素，因為他會是最後一個重複的元素。

Implement q_reverseK de50aac

使用 list_for_each_safe 遍歷鏈結串列

list_for_each_safe (curr, next, head) {
    if (++count != k)
        continue;

如果 count != k 的話跳過這個迴圈，達到 k 時，使用 q_reverse 的方法，把鏈結串列反轉

    while (count--) {
        next_element = element->next;
        list_move(element, group_start);
        element = next_element;
    }

反轉後，更新 group_start 為組最後一節點。

    group_start = next->prev;
}

Implement q_sort 743c731

實作 merge sort 為了美觀，我另外新增了兩個函式，一個做切分遞迴 _q_merge_sort ，一個做合併 _q_merge ，其實切分遞迴可以用原本的函式就好了。

先介紹 _q_merge

void _q_merge(struct list_head *l_head, struct list_head *r_head, bool descend)

目的是將兩個已經排序好的鏈結串列 l_head 和 r_head 合併成一個新的鏈結串列，並根據 descend 參數決定是升序還是降序。

我的做法是將右邊串列的第一個元素一個一個加到左邊串列，直到左邊串列頭碰到右邊串列頭，或是右邊串列的元素都被清空。

首先先取得左邊串列的第一個元素

{
    element_t *l = list_first_entry(l_head, element_t, list);

然後如果右邊串列不是空的的話，就重複迴圈，每次迴圈都先取得右邊串列第一個元素用於比較

    while (!list_empty(r_head)) {
        element_t *r = list_first_entry(r_head, element_t, list);

接著這個內層循環會用前面定義的 _q_value_cmpare 來比較 l 以及 r 元素的值，如果輸出小於等於 0（根據 descend 決定順序），則表示 l 已經在正確位置，繼續移動 l 到下一個元素，直到找到需要插入 r 的位置或 l 回到了 l_head 。

        while (&l->list != l_head && _q_value_cmpare(l->value, r->value, descend) <= 0)
            l = list_entry(l->list.next, element_t, list);

如果 l 回到了 l_head ，表示左右串列的所有元素都已經在正確位置。此時可以直接將右邊串列剩餘的部分追加到左邊串列的末尾，然後清空 r_head ，結束合併過程。這是一個優化步驟，能提升排序效率。

        if (&l->list == l_head) {
            // Append right list to left list
            l_head->prev->next = r_head->next;
            r_head->next->prev = l_head->prev;

            r_head->prev->next = l_head;
            l_head->prev = r_head->prev;

            INIT_LIST_HEAD(r_head);
            break;
        }

如果左編串列還有元素需要調整，將右鏈表的元素 r 插入到 l 的前面，完成一次合併操作。

        list_move_tail(r_head->next, &l->list);
    }
}

接著介紹 _q_merge_sort

void _q_merge_sort(struct list_head *head, bool descend)

這個函式通過遞迴從中細分串列直到當前陣列為單一元素，接著合併左右串列來完成整個串列的排序。

首先先判斷結束條件，用 list_is_singular 判斷當前的串列長度是否等於1，接著用之前定義過的函式 _q_find_mid 來取得串列的中間點；要切分的地方

{
    if (list_is_singular(head))
        return;

    struct list_head *l = head, *r = &(struct list_head) {},
                     *mid = _q_find_mid(head->next, head->prev),
                     *l_end = mid->prev;

從中間節點 mid 分割成兩個獨立的串列：左半部分以 l 為頭，右半部分以 r 為頭。

    r->next = mid;
    mid->prev = r;
    r->prev = l->prev;
    l->prev->next = r;

    l->prev = l_end;
    l_end->next = l;

對左半部分和右半部分分別進行遞迴排序，直到每個子串列都成為單一元素。

    _q_merge_sort(l, descend);
    _q_merge_sort(r, descend);

最後使用 _q_merge 將排序好的左半部分和右半部分合併成一個完整的排序串列。

    _q_merge(l, r, descend);
}

最後的最後 q_sort 只需要呼叫 _q_merge_sort(head, descend) ，就可以拿到排序好的串列。

Implement q_merge 4e501c7

這個函式輸入了一個 queue_contex_t 的鏈結串列，我先拿了第一個元素當作要合併到的目標 out

queue_contex_t *out = list_first_entry(head, queue_contex_t, chain), *node;

接著自訂一個迴圈從 out 的下一個元素開始，直到串列頭。
前面已經實作了 _q_merge ，就可以利用他將 node->q 鏈結串列追加到 out->q

for (node = element_next(out, chain); &node->chain != head;
    node = element_next(node, chain)) {
    _q_merge(out->q, node->q, descend);
}