2025q1 Homework1 (lab0)

contributed by < dainel40911 >

Reviewed by `Andrushika`

目前作業好像還沒有完成，我想我可以先對提交 commit 上給一些建議。
在 Commit bd74e0e 中，雖然標題寫 Implement q_free function，但仔細看內容，會發現也對 q_insert_head, q_insert_tail 等 function 做了修改。建議一個 commit 中不要包含太多無關的修改。

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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 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
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           126
Model name:                      Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
Stepping:                        5
CPU MHz:                         1200.000
CPU max MHz:                     3600.0000
CPU min MHz:                     400.0000
BogoMIPS:                        2380.80
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       128 KiB
L2 cache:                        2 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

中間發生環境問題

awk: line XX: regular expression compile failed (missing operand)
()
commit-msg.hook 腳本內的 TRAILERS_BY_REGEX 變數在 regex 組裝時，組成了空的 ()。
awk 無法解析空的正則 /()/，因此 crash。

q_new

目標

透過 malloc 分配 head 大小的記憶體空間
檢查 malloc 是否成功，若是失敗，返回 NULL
通過檢查後將 prev 以及 next 兩個指標指向 head ，最後 return head 。

改進: 參考了 HotMercury 在 HenryChaing 底下的建議，發現可以使用 linux list.h 提供的API進行檢查的改寫。

-    if (!head) {
+    if (list_empty(head)) {
         return NULL;
     }

改進: 後續發現可以用 list.h 中的 INIT_LIST_HEAD

q_free

目標

釋放整個佇列佔用的所有內存，包括佇列元素及其存儲的數據。

初始想法是透過 *next 去依序找到,後來發現可以直接使用 list.h 中的 list_for_each_entry_safe 去走訪每個節點，使用 list_del 將要刪除的節點從 list 中斷開，透過釋放每個元素佔用的記憶體。最後，釋放 head 節點的記憶體

q_insert_head

目標

在 list 的開頭插入一個元素，先創建一個新的element_t，為字串分配記憶體並複製輸入字串，透過 list_add() 將這個新元素加到佇列的開頭，若有任何的記憶體分配失敗，則返回 false。

q_insert_tail

目標

跟 q_insert_head 一樣的概念，只是變成將元素插入在尾部

後續看到教授在 chiangkd 的建議，採用 q_insert_head 來實作 q_insert_tail

q_remove_head and q_remove_tail

目標

從佇列的頭部或尾部移除一個節點
如果使用者提供緩衝區，會附註被移除節點內的字串給使用者
傳回被移除的節點的指標，若佇列釋空的或無效的話，則回傳 NULL
最多複製 bufsize-1 個字符，因為要留一個給 '\0'

q_delete_mid

目標

透過快、慢，兩個指標去找到中間點並移除