# 2025q1 Homework1 (lab0)
contributed by < `nyraa` >
### Reviewed by `Denny0097`
> commit 05e9815 前後的 commit 格式不一致

在 05e9815 前，commits 的 title 都會包含 function 要做的事，而之後的 commits 變成 title 只敘述建立的什麼 function ，建議統一。

### Reviewed by `rota1001`
1. 在 `q_delete_dup` 中（[queue.c#L128](https://github.com/nyraa/lab0-c/blob/master/queue.c#L128)），`strcmp(curr_e->value, safe_e->value) == 0` 可以改成 `!strcmp(curr_e->value, safe_e->value)` 較簡潔。
2. 這裡的 `q_delete_mid` 使用快慢指標實作，請思考如何充分運用雙向鏈結串列的優勢。
3. `q_ascend` 中多次使用 `printf`，請不要把除錯訊息留著。
4. `q_merge` 中，先進行合併後再依據 `descend` 去決定是否進行 `q_reverse`，這樣會造成問題。因為在進行 `merge_two_lists` 時，他是把兩個遞增的鏈結串列合併為一個遞增的鏈結串列，然而兩個遞減的鏈結串列卻不能合併成一個遞減的鏈結串列。所以當 `descend` 為 `true` 的時候結果會是錯的。

### Reviewed by `EricccTaiwan`
在 `q_insert_head` 可以用 `list_add` 取代，取代手動維護 `next`/`prev` 指標的四行程式碼，也增加可讀性。

-new->list.next = head->next;Add commentMore actions
-new->list.prev = head;
-head->next->prev = &new->list;
-head->next = &new->list;
+list_add(&new->list, head);

感謝參考我在 [`q_merge` 的實作](https://hackmd.io/BckFGTUbTba-PHY89cr9yQ?view#q_merge)，歡迎留言討論!

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## 開發環境

$ 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](https://github.com/nyraa/lab0-c/commit/05e98152ccdee5e1055334e1a100f4d90c4a4ca6)
### q_free
用 `list_for_each_safe` 迭代整個 queue ，然後釋放每個 element 的記憶體，`list_for_each_safe` 巨集允許移除當個節點。
最後再移除 head 節點。

> Commit [fa67ad6](https://github.com/nyraa/lab0-c/commit/fa67ad632bc72912685d1e55d115b921d338ea07)

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

> Commit [4130860](https://github.com/nyraa/lab0-c/commit/413086073aed121622fd5a19889c08a03b1729e6)
### q_insert_head
配置一個新個 `element_t` ，並且用 strdup 配置一個跟 `s` 相同長度的記憶體把 `s` 複製進新的 `element_t` ，接著用 `list_add` 加入 queue 最前方。

> Commit [f55568d](https://github.com/nyraa/lab0-c/commit/f55568df3ecf1e4fb85f35c3c5e68e33a1b4a45e)
### q_insert_tail
跟`q_insert_head`相似，只是插入的巨集用`list_add_tail`。

> Commit [caf276b](https://github.com/nyraa/lab0-c/commit/caf276b6d82454e1f411d269337d1d91c98403d2)
### q_remove_head
首先檢查 queue 是不是 NULL 或是 empty，接著用 `list_entry` 找出element，先將要刪除的 `value` 複製到 `*sp` ，然後刪掉 head 的下一個節點，並傳回element。

> Commit [dd0b205](https://github.com/nyraa/lab0-c/commit/dd0b205420286baf4aec61dcd236174c8691bc89)
### q_remove_tail
這個函式也是首先檢查 queue 是不是 NULL 或 empty，然後重複利用 `q_remove_head` 並傳入 `head->prev->prev` 來指向 tail 的前一個節點，讓 `q_remove_head` 來移除。
`head->prev->prev` 在 queue 不空的時候永遠指向 tail 前一個元素，因此可以這樣使用。

> Commit [dd0b205](https://github.com/nyraa/lab0-c/commit/caf276b6d82454e1f411d269337d1d91c98403d2)
### q_size
用 `list_for_each` 巨集迭代整個 queue，並計算節點數量並傳回。
這段程式來自作業需求中的第一步。

> Commit [aaae024](https://github.com/nyraa/lab0-c/commit/aaae024980842b8dd14e493f6853d003d564c1c9)
### q_delete_mid
用快慢指標技巧來找到中間的節點，然後刪除。

> Commit [bfe7d3a](https://github.com/nyraa/lab0-c/commit/bfe7d3aa6c33b2406e6d73e0171059702cc5f667)
### q_delete_dup
用 `list_for_each_safe` 來迭代整條鏈結串列，如果目前節點跟下一個節點是相同的，就移除目前節點，同時設定一個旗標，代表下一個節點與這一個節點也是相同的，假設下次迭代時，目前節點跟下一個節點不同，代表目前節點是上一段重複區域的尾端，也需要移除，並清除旗標。

> Commie [18c644b](https://github.com/nyraa/lab0-c/commit/18c644b5e238e9df7221949cb6faa2c8f626abb6)
### 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](https://github.com/nyraa/lab0-c/commit/c45a6f6cdb0838368fa9fdc97eb8409ab0fe7d13)
### q_descend
這個函式要將鏈結串列不符合降序的節點刪除。
作法跟 `q_ascend` 類似，只是紀錄最大值並移除較小值。

> Commit [c45a6f6](https://github.com/nyraa/lab0-c/commit/c45a6f6cdb0838368fa9fdc97eb8409ab0fe7d13)
### q_merge
這邊使用了兩層的迴圈，想法啟發於 [EricccTaiwan](https://github.com/EricccTaiwan/lab0-c/blob/master/queue.c#L337) 的作法，但是我做了調整。
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](https://github.com/nyraa/lab0-c/commit/eed672f653a5bf0e9da220526339fa105f8a1c16)
## 娃
我覺得我作不完，正在看論文。