2024q1 Homework2 (quiz1+2)

# 2024q1 Homework2 (quiz1+2) contributed by < `yutingshih` > 程式碼：[linux2024-quiz](https://github.com/yutingshih/linux2024-quiz) on GitHub ## 第一週測驗題 ### 測驗 1 #### 程式運作原理測驗題中提供的程式參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 所實作的非遞迴 (non-recursive; iterative) 快速排序法，以堆疊取代遞迴函式呼叫，避免後者所帶來的額外開銷。其中以 `begin` 和 `end` 兩個堆疊記錄串列中尚未排序好的部分，在每一輪迭代當中，會先選定 pivot 為串列首個節點，然後將整個串列分成比 pivot 小的左半部分、pivot 本身以及比 pivot 大的右半部分，並依序將其各自的起點及終點推入 `begin` 及 `end` 堆疊當中。例如：左半部分有 `A`、`B`、`C`、`D` 四個節點，pivot 為 `D` 節點，右半部分則有 `F`、`G`、`H` 三個節點 ``` left : A -> B -> C -> D pivot : E right : F -> G -> H ``` 接著將三者的起點和終點各自推入堆疊 ``` index | 0 1 2 3 4 ... 7 ------+--------------------- begin | A E D end | D E H ``` 在下一輪迭代則從堆疊中拿取其中的半邊，也就是子串列 `D` 到 `H` 繼續進行排序 #### 改進實作  ### 測驗 2 #### 程式運作原理先解釋 Timsort 實作中重要的函式功能及重點： - `find_run` 會從串列的開頭開始切出一段單調 (monotonic) 的子序列，若為遞減序列，則會將其調整為遞增序列後回傳 - `merge_at` 依照給定的比較函式 `cmp`，合併堆疊最上層的的兩個 runs - `merge_collapse` 則會檢查堆疊 `tp` 中最上層的三個 runs 是否滿足以下條件，若不滿足則挑選 `tp->prev->prev` 及 `tp` 中較短者與中間的 `tp->prev` 進行合併，用來確保被合併的兩個 runs 長度盡可能接近 - `tp->prev->prev` 長度大於 `tp->prev` 和 `tp` 的總和 - `tp->prev` 長度大於 `tp - `merge_force_collapse` 則不做上述條件的檢查，直接挑選 `tp->prev->prev` 及 `tp` 中較短者與中間的 `tp->prev` 進行合併 - `merge` 將兩串列合併後回傳 - `merge` 將兩串列合併後使用 `build_prev_link` 重建雙向環轉鏈結串列的鏈結 #### 改進實作 #### 整合  ## 第二週測驗題 ### 測驗 1 #### 程式運作原理  #### 測試程式  ### 測驗 2 #### 程式運作原理  #### 測試程式  ### 測驗 3 #### 程式運作原理 `find_nth_bit` 的功能是找到第 n 個為 1 的位元，回傳其為整個搜尋範圍中的第幾個位元，並 LSB (least significant bit) 定義為第 0 個位元，若找不到，則回傳搜尋範圍的大小 `size`。 `find_nth_bit` 使用到 `FIND_NTH_BIT` 巨集及 `fns` 函式 `fns` 函式透過重複呼叫 `__ffs` n 次來尋找一個字節 (word) 中第 n 個為 1 的位元的位置，每次呼叫 `__ffs` 後都會將該位元清空，連續呼叫 n 次就相當於尋找第 n 個為 1 的位元。 `GENMASK` 巨集產生自第 `l` 到第 `h` 位元為 1 的遮罩 (mask)，其中最低位編號為 0 `small_const_nbits` 檢查 `nbits` 是否為大於 0 且小於等於 `BITS_PER_LONG` 的常數 `__const_hweight8`、`__const_hweight16`、`__const_hweight32` 以及 `__const_hweight64` 分別計算最低數個位元當中有多少個為 1 的位元，`hweight_long` 則和 `__const_hweight64` 行為相同 `FIND_NTH_BIT` 首先逐字節判斷是否存在第 `num` 個位元為 1，若目標存在於當前字節，則呼叫 `fns` 函式尋找第 n 個為 1 的位元，找不到則直接回傳 `size`。