2025q1 Homework1 (lab0)

contributed by <gg21-aping>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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):                   4
  On-line CPU(s) list:    0-3
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
    CPU family:           6
    Model:                69
    Thread(s) per core:   2
    Core(s) per socket:   2
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   49%
    CPU max MHz:          2600.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4589.18

Reviewed by `MikazkiHikari`

請確認是否有按照預期進行rebase；然後 queue.[ch]的部分寫的很詳盡，但其他的項目呢?

資料結構和實作方式

element_t: the element to be linked in the queue, carrying a pointer to an array holding string.
queue_contex_t: can be considered as the config of the queue structure, carrying the pointer to the head of the queue, the size, and the id.

佇列實作：修改 `queue.[ch]`

`queue_new()`

參考 Linux Kernel 實作佇列，使用 INIT_LIST_HEAD()，將 list_head 的 next 和 prev 指標都指向結構本身。

`q_free()`

考量僅是將節點自佇列中移除，但不釋放其記憶體空間，可透過 list_for_each_entry_safe() 保存下個節點的指標，並逐一走訪佇列中各節點。

提交程式碼的時候遇到一些問題：

(resolved) 程式碼被判斷並沒有使用指定的 coding style。查 Linux 核心程式碼使用 list_for_each_entry_safe() 都沒有在函式名稱及 ( 間插入一個空白。

-    list_for_each_entry_safe(e, next, head, list) {
+    list_for_each_entry_safe (e, next, head, list) {
         q_release_element(e);
     }

[!] queue.c does not follow the consistent coding style.

Make sure you indent as the following:
    clang-format -i queue.c

感謝社團同學提出參考 Linux 核心程式碼對 .clang-format 的操作，新增 SpaceBeforeParens 並提出 PR。

(resolved) cppcheck 觸發的 unusedlabel 警告。參考 issue#211 的討論，只能將 cppcheck 從 ubuntu 24.04 LTS 的官方版本 2.13 再往上更新。Commit e0c6b11 解決了 unusedlabel 警告，但依然會觸發 uninitvar 警告。因此提了 issue#229 的討論。

Following files need to be cleaned up:
queue.c
Running static analysis...
queue.c:28:5: error: Uninitialized variable: next [uninitvar]
    list_for_each_entry_safe (e, next, head, list) {
    ^

Fail to pass static analysis.

`q_insert_head/tail()`

使用 strdup() 複製字串 s，避免原始的 s 指向的記憶體區塊被釋放或更動後影響到 e->value。

The strdup() function returns a pointer to a new string which is a
duplicate of the string s. Memory for the new string is obtained
with malloc(3), and can be freed with free(3).

strdup() 透過 malloc(strlen(s) + 1) 來動態分配記憶體空間，再透過 strcopy() 將原始字串的內容複製到新分配的記憶體。

todo:

在佇列中將節點插入頭或尾的操作基本相同，可以思考更有品味的程式碼。

`q_remove_head/tail()`

透過 list_entry() 系列操作可取得想要的節點資訊。注意 strncpy(*dest, *src, n) 在 destination 長度比 source 長度長的時候，會將剩餘空白的位置都自動補上終止符 \0，反之則 dest 指向的字串將不會有終止符。因此，為了避免呼叫者使用可能未正確終止的字串而導致的各種問題，做了一些防禦機制：

strncpy(sp, e->value, bufsize - 1);
sp[bufsize - 1] = '\0';

unlink 被認定是 american english，但 unlinked 或 unlinks 均不被 aspell 認定為 american english，Functions 也不被認定為 american english QQ

todo:

在佇列中移除頭或尾節點的操作基本相同，可以思考更有品味的程式碼。

`q_size()`

原本想透過 container_of() 直接使用 queue_contx_t 中的成員 size，但觀察 qtest.c 中對 q_size() 的呼叫，發現傳入的值有時是成員 q，有時是成員 chain。因此貿然的直接定位會無法取得正確的記憶體位置。因此仍是透過逐一走訪的方式計算。

`q_delete_mid()`

鏈結的中間節點可以透過兩次走訪鏈結取得，但透過 Hare and Tortoise Algorithm（快慢指標），我們可以只走訪鏈結一次，便快速定位到中間節點。僅需特別注意的是，此作業提供的結構為 circular doubly linked list，亦即指標不會指向 NULL，且單一節點便能取得其連結的前後節點。

注意 list_del() 並不會釋放記憶體空間，僅是將該節點從鏈結中移除。節點仍會存在，但其指標指向的位址不能被保證；若要再次將節點加入鏈結中，依然要先呼叫 LIST_INIT_HEAD()。

`q_delete_dup()`

在 queue.h 的註解中，並沒有提到所有呼叫此函式的鏈結都是有序的，但卻附上 leetcode 刪除有序鏈結中的重複節點。所以一開始會有點不太確定課程期待的寫法是什麼。若能保證是有序鏈結，那麼透過雙指標，就能有效率的完成刪除重複節點的行為。但若無法保證傳入的鏈結為有序，就需要透過例如雜湊表的方式，來達到最佳的效能。

參考數位同學的解法，推估該函式就是預設傳入的節點都為有序，因此先透過雙指標的方式完成此函式。逐一走訪佇列中各項元素，並透過 strcmp 做 char 的比較。

其中 strcmp() 規定傳入的字串必須是 null-ended strings（即字串必須是 \0 結尾），雖然在 queue.h 中並未明定，但若節點的 value 成員不存在，設定回傳 false。

+    list_for_each_entry_safe(cur, next, head, list) {
+        if (&next->list == head)
+            break;
+    
+        if (!cur->value || !next->value)       
+            return false;
+
+        if (!strcmp(cur->value, next->value)) {
+            list_del(&cur->list);
+            q_release_element(cur);
+        }
+    }

後來發現我把題目理解成 A -> B -> B -> C 要變成 A -> B -> C 的意思，但其實應該要把 B 完全移除。所以又做了以下修正。透過變數 should_delete 紀錄最後一個重複節點，並進行刪除。

     element_t *curr = NULL, *next = NULL;
+    bool should_delete = false;

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

     list_for_each_entry_safe(curr, next, head, list) {
-        if (&next->list == head)
-            break;
+        bool duplicate =
+            (&next->list != head && !strcmp(curr->value, next->value));

-        if (!curr->value || !next->value)
-            return false;
-
-        if (!strcmp(curr->value, next->value)) {
+        if (duplicate || should_delete) {
             list_del(&curr->list);
             q_release_element(curr);
+            should_delete = duplicate;
         }
     }

`q_swap()`

透過兩個指標，並使用 list_move() 可以快速的完成兩兩一組的交換操作。此時，curr 指向一組節點中的第一個節點，而 next 指向下一組節點中的第一個節點。

curr = head->next;
while (curr != head && curr->next != head) {
    next = curr->next->next;
    list_move(curr->next, curr->prev);
    curr = next;
}

更新：可透過呼叫 q_reverseK(head, 2) 來取代原本的 swap 操作。

`q_reverse()`

透過逐一走訪各節點並呼叫 list_move() 將各節點移至 head 節點後，即可完成整串鏈結的反轉。

`q_reverseK()`

透過三個指標 start、end 和 iter 來做鏈結的部分反轉。

start = head; 
while (size >= k) {
    struct list_head *end = start->next, *iter = start->next;
    
    for (i = 0; i < k; i++) {
        list_move(iter, start);
        iter = end->next;
    }
    
    start = end;
    size -= k;
}

有特別注意變數宣告的位置，原本將 end 和 iter 一起宣告在整個函式區塊的最頂部 (beginning of the block)；但考慮該二變數僅在迴圈中使用，應定義在最小作用域的程式碼區塊中的最頂部，因此做了修正。

`q_sort()`

考量到資料結構為鏈結串列，使用 merge sort 的方式對鏈結進行排序。概念如下：

透過快慢指針找到鏈結的中間點，透過 list_cut_position() 進行切分。
遵循 divide and conquer 的概念，透過遞迴手法不斷進行上述的切分行為。
呼叫 helper function q_merge_two() 進行排序。
參考 yuto0226 同學的筆記，新增 is_descend() 函式來判斷排序順序。

`q_ascend/descend()`

題目要求將所有破壞升序、降序法則的節點刪除，即在升序的鏈結串列中，較小的元素不能在後面出現，降序則反。若從鏈結的起點開始往後走，判斷上會非常困難。但若從尾部開始往前走，則僅需紀錄一個 extreme 值，在升序排列中，遇到比 extreme 大的值一律刪除，在降序排列中則反。

因此我首先寫了 list_for_each_entry_safe_reverse 的 macro 來協助我完成安全的迴圈操作。

/* Iterate through a list reversely */
#define list_for_each_entry_safe_reverse(entry, safe, head, member)    \
    for (entry = list_entry((head)->prev, typeof(*entry), member),     \
        safe = list_entry(entry->member.prev, typeof(*entry), member); \
         &entry->member != (head); entry = safe,                       \
        safe = list_entry(safe->member.prev, typeof(*entry), member))

並創建一個 q_make_monotonic() 的函式，透過對變數 descend 的控制，即可讓 q_ascend() 和 q_descend() 同時呼叫。

/**
 * q_make_monotonic() - Remove nodes to make queue monotonic
 * @head: header of queue
 * @descend: whether to filter for descending (true) or ascending (false)
 *
 * Return: the number of elements in queue after performing operation
 */
static int q_make_monotonic(struct list_head *head, bool descend)
{
    element_t *curr, *next;
    char *extreme = NULL;

    if (!head || list_empty(head) || list_is_singular(head))
        return q_size(head);

    list_for_each_entry_safe_reverse(curr, next, head, list)
    {
        if (!extreme) {
            extreme = curr->value;
            continue;
        }
        if (is_descend(extreme, curr->value, descend)) {
            list_del(&curr->list);
            q_release_element(curr);
        } else {
            extreme = curr->value;
        }
    }

    return q_size(head);
}

`q_merge()`

藉由之前完成 q_sort() 開發過的 q_merge_two()，用暴力解的方式，兩兩合併在一起。

2025q1 Homework1 (lab0)

開發環境

Reviewed by MikazkiHikari

資料結構和實作方式

佇列實作：修改 queue.[ch]

queue_new()

q_free()

q_insert_head/tail()

todo:

q_remove_head/tail()

todo:

q_size()

q_delete_mid()

q_delete_dup()

q_swap()

q_reverse()

q_reverseK()

q_sort()

q_ascend/descend()

q_merge()

Read more

2025q1 Homework2 (quiz1+2)

2025q1 Homework1 (ideas)

Reviewed by `MikazkiHikari`

佇列實作：修改 `queue.[ch]`

`queue_new()`

`q_free()`

`q_insert_head/tail()`

`q_remove_head/tail()`

`q_size()`

`q_delete_mid()`

`q_delete_dup()`

`q_swap()`

`q_reverse()`

`q_reverseK()`

`q_sort()`

`q_ascend/descend()`

`q_merge()`