2025q1 Homework1 (lab0)

contributed by < ericlin1231 >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [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 (GCC) 14.2.1 20241116
Copyright (C) 2024 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):                   28
  On-line CPU(s) list:    0-27
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-14700KF
    CPU family:           6
    Model:                183
    Thread(s) per core:   2
    Core(s) per socket:   20
    Socket(s):            1
    Stepping:             1
    CPU(s) scaling MHz:   19%
    CPU max MHz:          5600.0000
    CPU min MHz:          800.0000
    BogoMIPS:             6835.20
    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 bt
                          s rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 mo
                          nitor ds_cpl vmx est tm2 ssse3 sdbg fma 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 ssbd 
                          ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi
                          1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec
                           xgetbv1 xsaves split_lock_detect user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_notify 
                          hwp_act_window hwp_epp hwp_pkg_req hfi vnmi umip pku ospke waitpkg gfni vaes vpclmulqdq rdpid
                           movdiri movdir64b fsrm md_clear serialize arch_lbr ibt flush_l1d arch_capabilities
Virtualization features:  
  Virtualization:         VT-x
Caches (sum of all):      
  L1d:                    768 KiB (20 instances)
  L1i:                    1 MiB (20 instances)
  L2:                     28 MiB (11 instances)
  L3:                     33 MiB (1 instance)
NUMA:                     
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-27

實作佇列操作

q_new

Commit

宣告 head 指標指向 malloc 配置的記憶體空間，其大小為 sizeof(struct list_head)，透過 INIT_LIST_HEAD 將其初始化

q_free

Commit 1: 第一次提交
Commit 2: 修正未釋放 value 記憶體空間的問題

先對 head 為 NULL 和 queue 為空的狀況進行檢查，再使用巨集 list_for_each_safe 逐一走訪內嵌於 element_t 中的 struct list_head list，再透過 container_of 推算節點的記憶體位址，然後使用 free 將節點釋放

q_insert_head

Commit 1: 第一次提交
Commit 2: 添加 String Format 到 snprintf 中

替節點配置記憶體空間並且替 value 配置記憶體空間，要注意若 value 的記憶體空間配置失敗，需要將配置給節點的記憶體空間釋放以免造成記憶體洩漏，透過 snprintf 將輸入字串複製到 value 中，因為原本由 string.h 提供的 strncpy 不會對字串長度進行檢查，可能產生安全問題，透過作業腳本提供的資訊，我找到提供字串長度檢查的 snprintf，可以找到 FreeBSD 類似的實作，最後透過 list.h 提供的 list_add 將節點加到佇列的頭

q_insert_tail

Commit 1: 第一次提交
Commit 2: 添加 String Format 到 snprintf 中

跟 q_insert_head 的概念相同，但是最後是用 list_add_tail

q_remove_head

Commit

使用 container_of 得知內嵌 list_head 的節點的記憶體位址，然後再用 snprintf 將節點中 value 的內容複製到 sp 當中，最後用 list.h 提供的 list_del 將節點從佇列中移除

q_remove_tail

Commit

概念和 q_remove_head 相同，q_remove_head 透過 head->next 移除節點，而 q_remove_tail 透過 head->prev 移除節點

q_delete_mid

Commit

透過兩個指標 next 和 prev 分別往右和左訪問節點，直到重疊就可以找到中間節點將其刪除，要注意除了節點以外，value 佔用的記憶體空間也要釋放

q_delete_dup

q_swap

Commit

使用類似快慢指標的技巧，把第一個節點當作 head，第二個節點當作佇列的第一個元素，使用 list_move 將第三個節點移動到佇列的頭，等同於 Swap 操作

q_reverse

Commit

反轉佇列只需要將每一個節點的 next 和 prev 指標交換就好，我嘗試使用 Bit Wise XOR 交換，發現對於指標型態的資料，直接用 XOR 對其中的資料進行運算是不合法的，將其強制轉型為 uintptr_t 的指標型態，就可以對其進行運算，而 uintptr_t 定義在 stdint.h 中，其相當於 unsigned long int

q_reverseK

q_sort

q_ascend

q_descend

q_merge