# 2024q1 Homework2 (quiz1+2)
contributed by < `shlin41` >

---
## 第一週測驗題
---
### 測驗一
#### 運作原理
程式碼的運作概念上和 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 相同，都是把原本的鏈結串列分成大於 `pivot`，和小於 `pivot` 的兩個子鏈結串列。只是運作方式上有所不同。運作方式如下：

利用 `node_t *begin[max_level], *end[max_level];` 模擬堆疊的運作。每一對指標 `{begin[i], end[i]}` 代表尚未完成排序的子鏈結串列。

每次從堆疊中拿出一對指標，進行子鏈結串列的排序處理。雖說是排序處理，但是主要工作是把子鏈結串列再分成三個孫鏈結串列，再放回堆疊中。處理的方式如下：
* 取子鏈結串列的頭節點當成 `pivot`
* 節點小於等於 `pivot` 的，串成一個孫鏈結串列 `left`
* `pivot` 自成一個孫鏈結串列
* 節點大於 `pivot` 的，串成一個孫鏈結串列 `right`

假設原本的子鍵結串列如下：

digraph structs {
    node[shape=plaintext];
    pivot [fontcolor="red"];
    L [fontcolor="blue"];
    R [fontcolor="blue"];
    
    node[shape=box];
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    {
        rank="same";
        struct0 -> struct1
        struct1 -> struct2
        struct2 -> struct3
        struct3 -> struct4
    }
    pivot -> struct0;
    L -> struct0;
    R -> struct4;
}

完成處理後的三個孫鍵結串列如下：

digraph structs{
    node[shape=plaintext];
    left [fontcolor="blue"];
    pivot [fontcolor="red"];
    right [fontcolor="blue"];
    node[shape=box]
    struct0 [label= "4"];
    struct1 [label= "5"];
    struct2 [label= "3"];
    struct3 [label= "2"];
    struct4 [label= "1"];
    pivot -> struct0;
    left -> struct2;
    struct2 -> struct3;
    struct3 -> struct4;
    right -> struct1;
}

邊界條件：從堆疊中取出來的子鍵結串列長度為 1 時，將其加到最終的鍵結串列 `result` 中。等到堆疊為空時，結束排序程式並回傳 `result`。

#### 改進方案
改進方案的實做將直接併入 Linux 核心風格的 List API 一起處理。程式碼可改進的地方：
* 將單向鍵結串列，修改成雙向鍵結串列。如此可以加速 `list_tail()` 的執行。直接使用 `struct list_head` 即可。
* [TBD] pivot 的挑選要隨機，如此可以避開 worst case (排序 descending order 的鍵結串列)。但是，「如何快速從鍵結串列中隨機挑選一個節點」又是一個問題。
* 原本的程式碼使用固定長度的陣列堆疊 `node_t *begin[max_level], *end[max_level];`。可以直接使用學習第一份作業 (lab0-c) 的 `queue_contex_t`，使用一個雙向鍵結串列來模擬堆疊。則堆疊可以動態增減。

#### Linux 核心風格的 List API 改寫
[Source Code](https://github.com/shlin41/quick_sort)

導入 struct list_head 進 node_t 中

typedef struct __node {
    long value;
    struct list_head list;
} node_t;

為了處理堆疊，新增一個資料結構

typedef struct __chain {
    struct list_head head; // used for storing un-sorted list of node_t
    struct list_head chain; // used for simulate stack
} chain_t;

`quick_sort()` 的作法類似。每次從堆疊中拿出一個未完成的串列，然後拆解成 `left, middle, right` 三個串列，再放回堆疊中。這邊多定義一個 `middle` 用來儲存 `pivot`。

底下為資料結構示意圖：

---
### 測驗二
#### 運作原理
`timsort()` 運作方式:
* 以單向鍵結串列進行排序，且頭節點也是正常節點，而非單純的 `struct list_head`。一般 List API 不能使用。
* `list_head.prev` 被用來做其他用途。
* 頭節點的 `list_head.prev` 串成一個單向鍵結串列，用以模擬堆疊
* 第個二節點的`list_head.prev` 用來儲存鍵結串列長度
* 在 while-loop 中
* 利用 `find_run()` 把整個串列切成單調遞增的子串列。資料結構如下圖:
* 利用 `merge_collapse()` 進行提早合併。(合併規則可參考題目)
* 利用 `merge_force_collapse()` 把堆疊中的子串列合併至兩個以下。
* 最後用 merge_final() 或 build_prev_link() 把單向鍵結串列恢復成雙向鍵結串列。

merge() 運作方式
* 使用一般的 merge sort，並沒有採用 Galloping mode

#### 改進方案
目前的程式並沒有實作 minrun 和 Galloping mode。這兩部份可以是改進的方向。
不過，Galloping mode 的策略，在這種非連續記憶體的鍵結串列中，無法發揮功能。原因如下：
* 要採用這個策略，必須利用串列已排序的特性，使用二分搜尋法快速找到節點。
* 非連續記憶體無法使用二分搜尋法，無法提高合併速度。
*
[TBD: minrum]

#### 整合 timsort 進 lab0-c
[Source Code](https://github.com/shlin41/lab0-c/tree/dev_timsort)
未完成: 目前只能遞增排序 (descend 功能未完成)

---
## 第二週測驗題
---
### 測驗一
剛完成填空

---
### 測驗二
剛完成填空

---
### 測驗三
#### 運作原理
`find_nth_bit()` 運作原理：分成三種狀況
* `n >= size`: 直接回傳 size
* `64 >= size >= 1`: 在一個 `unsigned long` 裡面找 nth bit
* `GENMASK(h, l)`: 從 `l-bit` 到 `h-bit` 設定為 1，其他 bits 為 0
* `fns()`: 呼叫 n 次 `__ffs()`，並用 `__clear_bit()` 把對應的 bit 清為 0
* 其他狀況: 呼叫 `FIND_NTH_BIT()`

`__ffs()` 運作原理: 使用二分法找出第一個`bit == 1` 的位置

`__builtin_constant_p(nbits)`: 用於判斷 nbits 是否在編譯時期為常數

`FIND_NTH_BIT(addr[idx], size, n)`: 定義方式很特殊
* 該巨集會從 addr 開始，以一個 unsigned long 基本單位，一個一個往下找，找到第 n 個 `bit == 1` 的位置。
* `hweight_long(tmp)`: 找出 `unsigned long tmp` 這個變數裡，有幾個 1
* `#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))`:
==這個巨集太神奇了==。為什麼這樣可以找出 mask?
* 在 2's complement 中，`-var` 和 `64-var` 在 `0bXXXXXX` 的值是一樣的。每 64 一個循環。
* 我們需要往右移 `64 - nbits % 64 == -nbits`。

#### Linux 應用案例
[TBD]