2025q1 Homework1 (lab0)

contributed by < nyraa >

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [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:             Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
    CPU family:           6
    Model:                142
    Thread(s) per core:   2
    Core(s) per socket:   4
    Socket(s):            1
    Stepping:             12
    CPU(s) scaling MHz:   31%
    CPU max MHz:          3900.0000
    CPU min MHz:          400.0000
    BogoMIPS:             3600.00
    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_goo
                          d nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes6
                          4 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid s
                          se4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx
                           f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs 
                          ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad 
                          fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid mpx rdseed a
                          dx smap clflushopt intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm
                           ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi md_c
                          lear flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    128 KiB (4 instances)
  L1i:                    128 KiB (4 instances)
  L2:                     1 MiB (4 instances)
  L3:                     6 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-7
Vulnerabilities:          
  Gather data sampling:   Mitigation; Microcode
  Itlb multihit:          KVM: Mitigation: VMX disabled
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Mitigation; Clear CPU buffers; SMT vulnerable
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; Enhanced IBRS
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitizat
                          ion
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB fill
                          ing; PBRSB-eIBRS SW sequence; BHI SW loop, KVM SW loop
  Srbds:                  Mitigation; Microcode
  Tsx async abort:        Not affected

序列的操作

q_new

透過配置一個新的 list_head 並用 INIT_LIST_HEAD 巨集來初始化 queue 的開頭，產生一個 empty queue。

Commit 05e9815

q_free

用 list_for_each_safe 迭代整個 queue ，然後釋放每個 element 的記憶體，list_for_each_safe 巨集允許移除當個節點。
最後再移除 head 節點。

Commit fa67ad6

接著發現剛才沒有處理到 q_new 失敗時，傳入的 head 有可能是 NULL 的情況，會導致在迭代的時候對 NULL 指標操作而發生錯誤，因此加入檢查 head 是否為 NULL 的判斷在最上方。

Commit 4130860

q_insert_head

配置一個新個 element_t ，並且用 strdup 配置一個跟 s 相同長度的記憶體把 s 複製進新的 element_t ，接著用 list_add 加入 queue 最前方。

Commit f55568d

q_insert_tail

跟q_insert_head相似，只是插入的巨集用list_add_tail。

Commit caf276b

q_remove_head

首先檢查 queue 是不是 NULL 或是 empty，接著用 list_entry 找出element，先將要刪除的 value 複製到 *sp ，然後刪掉 head 的下一個節點，並傳回element。

Commit dd0b205

q_remove_tail

這個函式也是首先檢查 queue 是不是 NULL 或 empty，然後重複利用 q_remove_head 並傳入 head->prev->prev 來指向 tail 的前一個節點，讓 q_remove_head 來移除。
head->prev->prev 在 queue 不空的時候永遠指向 tail 前一個元素，因此可以這樣使用。

Commit dd0b205

q_size

用 list_for_each 巨集迭代整個 queue，並計算節點數量並傳回。
這段程式來自作業需求中的第一步。

Commit aaae024

q_delete_mid

用快慢指標技巧來找到中間的節點，然後刪除。

Commit bfe7d3a

q_delete_dup

用 list_for_each_safe 來迭代整條鏈結串列，如果目前節點跟下一個節點是相同的，就移除目前節點，同時設定一個旗標，代表下一個節點與這一個節點也是相同的，假設下次迭代時，目前節點跟下一個節點不同，代表目前節點是上一段重複區域的尾端，也需要移除，並清除旗標。

Commie 18c644b

q_swap

呼叫 reverseK 代入 2 ，相當於 q_swap 的需求，每兩個元素一組交換。

q_reverse

用 list_for_each_safe 迭代鏈結串列，然後一一用 list_move 巨集移動到 head，相當於將順序反轉。

q_reverseK

將鏈結串列迭代時，每 k 個元素用 list_cut_position 巨集切出一個 sub-list ，然後呼叫 q_reverse 來反轉 sub-list ，接著用 list_splice 接回原本的地方。

q_sort

新增了兩個 helper function ，分別是 merge_two_lists 跟 merge_sort，
merge_two_lists 是將兩條排序完的 list 做合併，以及透過 top-down 的 merge sort 來排序鏈結串列，最後看升序或是降序再做反轉。

q_ascend

這個函式要將鏈結串列不符合升序的節點刪除。
作法是從右方迭代向左掃描，並紀錄最小值，假設找到大於目前最小值的節點就移除，或是更新最小點。

Commit c45a6f6

q_descend

這個函式要將鏈結串列不符合降序的節點刪除。
作法跟 q_ascend 類似，只是紀錄最大值並移除較小值。

Commit c45a6f6

q_merge

這邊使用了兩層的迴圈，想法啟發於 EricccTaiwan 的作法，但是我做了調整。
EricccTaiwan 的作法是在外層迴圈用與 chain 長度除以二向上取整的次數，內層迴圈取每兩個鏈結串列為一對，並用 merge_two_list 來合併，並將結果放在第一條鏈結串列，將第二條鏈結串列移至 chain 的尾端，直到迭代至兩條其中一條為空鏈結串列，這邊預期的空鏈結串列是由前面合併拋到後面的空鏈結串列。

/* Implement from EricccTaiwan */
int size = q_size(head);
int m = (size >> 1) + (size & 1);

for (int i = 0; i < m; i++) {
    queue_contex_t *first = list_first_entry(head, queue_contex_t, chain);
    queue_contex_t *second =
        list_entry(first->chain.next, queue_contex_t, chain);

    while (!list_empty(first->q) && !list_empty(second->q)) {
        /* do merge and move second list to tail */
    }
}

這樣會碰到一個問題，假設在合併前已經有空的鏈結串列在 queue chain 中，內層迴圈在碰到這條鏈結串列之後就回終止迴圈，而不會繼續合併後續的鏈結串列。
我做出的修改是外層迴圈檢查 chain 的長度直到為 1 ：

int len = q_size(head);
while (len > 1) {
    ...
}

這是 q_merge 的目標，內層的迴圈是跑 ⌊len / 2⌋ 次，因為每兩條一對，假如為奇數條，我會將這條留到下一次再合併，這樣內層的迴圈跑的次數是由 len 決定的，不會有碰到空的鏈結串列就終止的問題：

int len = q_size(head);
while (len > 1) {
    for (int i = 0; i < (len >> 1); ++i) {
        /* do merge and put second list to tail */
    }
    len = (len >> 1) + (len & 1); 
}

因為合併是兩兩一對，每次 for 迴圈終止之後，len 會除以二，並因為合併時如果有多餘的一條則不會處理，所以如果 len 長度為奇數的時候需要加一，這樣合併直到 len 為 1。

最後再根據 descend 參數決定要不要反轉鏈結串列。

Commit eed672f

娃

我覺得我作不完，正在看論文。