2025q1 Homework1 (lab0)

contributed by < MuChengChen >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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

$ 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:             11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family:           6
Model:                140
Thread(s) per core:   2
Core(s) per socket:   4
Socket(s):            1
Stepping:             1
CPU(s) scaling MHz:   21%
CPU max MHz:          4200.0000
CPU min MHz:          400.0000
BogoMIPS:             4838.40
Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_
                      tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg f
                      ma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l2 cdp_l2 
                      ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdt_a avx512f avx512dq rdseed 
                      adx smap avx512ifma clflushopt clwb intel_pt avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves split_lock_detect user_shstk dtherm ida arat pln
                       pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopc
                      ntdq rdpid movdiri movdir64b fsrm avx512_vp2intersect md_clear ibt flush_l1d arch_capabilities
Virtualization features:  
Virtualization:         VT-x
Caches (sum of all):      
L1d:                    192 KiB (4 instances)
L1i:                    128 KiB (4 instances)
L2:                     5 MiB (4 instances)
L3:                     8 MiB (1 instance)
NUMA:                     
NUMA node(s):           1
NUMA node0 CPU(s):      0-7
Vulnerabilities:          
Gather data sampling:   Mitigation; Microcode
Itlb multihit:          Not affected
L1tf:                   Not affected
Mds:                    Not affected
Meltdown:               Not affected
Mmio stale data:        Not affected
Reg file data sampling: Not affected
Retbleed:               Not affected
Spec rstack overflow:   Not affected
Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, KVM SW loop
Srbds:                  Not affected
Tsx async abort:        Not affected

佇列操作實作

q_new

目的

創造空佇列

實作流程

1. 用 malloc 取得 list_head 結構體大小的記憶體空間並配置給新的 list_head 結構體指標，若記憶體取得失敗則回傳 NULL
2. 利用 INIT_LIST_HEAD 初始化 list_head 結構體指標，將指向的結構體的 next 和 prev 指向結構體本身
3. 回傳 list_head 結構體指標

q_free

目的

釋放所有佇列使用到的記憶體空間

實作流程

1. 使用 while 迴圈疊代佇列的所有節點
2. 使用巨集 container_of 取得節點的位址
3. 使用 list_del 斷掉節點與佇列的連結
4. 使用 q_release_element 釋放節點使用的記憶體
5. 當釋放完所有節點使用的記憶體後釋放佇列的 head

q_insert_head

目的

插入新的節點到佇列的第一個節點，且節點中的 value 和 s 字串的內容相同

實作流程

1. 若 head 和 s 為 NULL 回傳 false
2. 用 malloc 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 malloc 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 strncpy 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 list_add 將新的 element_t 結構體連接到佇列的第一個節點並回傳 true

q_insert_tail

目的

插入新的節點到佇列的最後一個節點，且節點中的 value 和 s 字串的內容相同

實作流程

1. 若 head 和 s 為 NULL 回傳 false
2. 用 malloc 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 malloc 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 strncpy 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 list_add_tail 將新的 element_t 結構體連接到佇列的最後一個節點並回傳 true

q_remove_head

目的

將佇列的第一個節點移除，且將節點中的 value 字串複製到字串 sp

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 container_of 取得佇列第一個節點的位址
3. 若 sp 不為 NULL 則使用 strncpy 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 list_del 斷掉節點與佇列的連結並回傳節點的位址

q_remove_tail

目的

將佇列的最後一個節點移除，且將節點中的 value 字串複製到字串 sp

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 container_of 取得佇列最後一個節點的位址
3. 若 sp 不為 NULL 則使用 strncpy 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 list_del 斷掉節點與佇列的連結並回傳節點的位址

q_size

目的

取得該佇列節點的數量

實作流程

1. 若 head 為 NULL 則回傳 0
2. 利用 list_for_each 疊代佇列中所有的節點並加總節點的數量，最後回傳該數量

q_delete_mid

目的

移除並釋放佇列中間的節點

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 false
2. 若佇列只有一個節點則移除並釋放此節點
3. 若佇列不只有一個節點則使用快慢指標的方法找到佇列中間的節點
4. 使用巨集 container_of 找到該節點的位址
5. 使用 list_del 斷開節點和佇列的連結
6. 釋放節點所使用的記憶體並回傳 true

q_delete_dup

目的

移除並釋放佇列中有相同value的相鄰節點

實作流程

1. 若 head 為 NULL 或佇列為空佇列回傳 false
2. 若只有一個節點回傳 true
3. 配置10個 char 大小的記憶體提供暫時存放節點的 value 的空間
4. 使用 list_for_each_safe 疊代佇列的所有節點
5. 若此節點的 value 與前一個節點(暫時存放的節點的 value )相同或是與下一個節點的 value 相同則暫時存放此節點的 value ，斷開此節點與佇列的連結並且釋放此節點使用的記憶體
6. 若此節點的 value 與前一個節點不同或是與下一個節點的 value 不同則將暫時存放節點的空間都存入空字串
7. 最後釋放配置的10個 char 大小的記憶體並回傳 true

q_swap

目的

交換佇列中每兩個節點的位置

實作流程

1. 使用 list_for_each_safe 疊代佇列中的每個節點，將 node 和 safe 的位置交換
2. 若全部節點都疊代過了或是只剩下一個節點還沒疊代則停止疊代

q_reverse

目的

倒置佇列中的節點

實作流程

1. 使用 list_for_each_safe 疊代佇列中的所有節點
2. 使用 list_move 將每個疊代到的節點移動成佇列的第一個節點

q_reverseK

目的

將佇列中每 k 個節點視為一個要倒置的 list ，若疊代至最後不足 k 個節點則不進行倒置

實作流程

1. 使用 list_for_each_safe 疊代佇列中的所有節點
2. 使用 list_move 將每個疊代到的節點移動成當前要倒置的 list 的第一個節點
3. 檢查是否已倒置 k 個節點，若已倒置 k 個節點則檢查剩下在佇列中未疊代到的節點數量是否大於或等於 k ，若是則紀錄此 list 的最後一個節點為接下來的 list 中要移動到的位置的前一個節點

q_sort

目的

將佇列中的節點依節點的 value 進行升冪或降冪的排序

實作方法

merge sort

實作流程

1. 將佇列的 head 分離，並初始化 head
2. 將佇列進行 merge sort 排序，以分治法實作
3. 使用快慢指標找到佇列的中點並以此分割成兩個佇列，以此遞迴分割直到每個佇列只剩下一個節點或沒有節點
4. 將分割完的佇列使用 strcmp 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將一開始分離的 head 接上佇列

q_ascend

目的

將節點中的佇列依升冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

實作流程

1. 使用 q_sort 進行升冪排序
2. 使用 list_for_each_safe 疊代排序好的佇列中的節點
3. 使用 strcmp 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 list_del 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

q_descend

目的

將節點中的佇列依降冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

實作流程

1. 使用 q_sort 進行降冪排序
2. 使用 list_for_each_safe 疊代排序好的佇列中的節點
3. 使用 strcmp 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 list_del 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

q_merge

目的

合併所有佇列並且以升冪或降冪排序

實作流程

1. 若串聯 queue_contex_t 的佇列的 head 為 NULL 或是佇列為空佇列則回傳 0
2. 疊代所有的 queue_contex_t ，每個 queue_contex_t 含有一個佇列
3. 將疊代到的佇列與第一個佇列的 head 分離並且初始化兩個佇列的 head
4. 使用 strcmp 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將第一個佇列的 head 接上合併好佇列
6. 若所有佇列皆已合併到第一個佇列則使用 list_for_each 疊代此佇列的所有節點以此計算節點的總數，最後回傳佇列中節點的總數