# 2025q1 Homework2 (quiz1+2)
contributed by < [HeLunWu0317 ](https://github.com/HeLunWu0317)>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}

## quiz1
### 測驗一
引入架構list.h

#include <stddef.h>
typedef struct list_item {
    int value;
    struct list_item *next;
} list_item_t;

typedef struct {
    struct list_item *head;
} list_t;

以此架構實作：list_insert_before

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC);
    *p = item;
    DDDD = before;
}

以 `p` 做 pointer to pointer 指向`list` l, l從`head`開始,故:
AAAA 為 `&l->head`
接下來, 設置結束條件,也就是當找到 insert 目標 node `before`，因此：
BBBB 為 'before'
最後做 node 移動，因為 p 為 pointer to pointer 做 p 指向的指標的移動，所以：
CCCC 為 '&(*p)->next'

最後結果 `*p` 指向 `before` 之前的 node ，將 item 做 insert , 並將 `item->next` 指向 `before`，因此：
DDDD 為 `item->next`

### 延伸問題：合併排序

list_item_t *list_split(list_item_t *head)
{
    if(!head || !head->next){
        return NULL;
    }
    //快慢指標尋找中間值
    list_item_t *slow = head;
    list_item_t *fast = head->next;

    while(fast->next && fast){
        slow = slow->next;
        fast = fast->next->next;
    }

    list_item_t *t2 = slow->next;
    slow->next = NULL;
    return t2;

}
list_item_t *list_merge(list_item_t *t1, list_item_t *t2)
{
    if (!t1){
        return t2;
    } 
    if(!t2){
        return t1;
    }

    list_item_t *final;
    //比較並且放入final list
    if (t1->value <= t2->value) {
        final = t1;
        final->next = list_merge(t1->next, t2);
    } else {
        final = t2;
        final->next = list_merge(t1, t2->next);
    }
    return final;
}

list_item_t *list_merge_sort(list_item_t *head)
{
    if (!head || !head->next)
    {
        return head;
    } 

    // 分割
    list_item_t *t2 = list_split(head);

    // 遞迴排序
    head = list_merge_sort(head);
    t2 = list_merge_sort(t2);

    // 合併
    return list_merge(head, t2);
}

### 測驗2
觀察程式碼，EEEE和FFFF所在程式碼區塊都是為了尋找可以使用的 target node ，當target node 擁有 children ，則要尋找替代 parent。
根據註解，尋找替代是透過 inorder 方式，找到左子樹中的最右 node ，`pred_ptr`指向左子樹，程式碼進入：

while(EEEE)
    pred_ptr = FFFF;

推測: 停止條件為，當找不到右 node 時，表示前一步 subtree 擁有最右 node。
因此:
* EEEE (迭代尋找)：(*pred_ptr)->r
* FFFF (目標): &(*pred_ptr)->r

#### 補全程式碼

目前需要補全的程式碼包括：
1. `find_free_tree` : 透過迭代搜尋 BST 中的 target node 的指標位置。
2. `find_predecessor_free_tree`: 透過迭代尋找左子樹中最大的節點(可在尋找替代時使用)。
3. `insert_free_node`:使用 BST 插入法，插入空閒節點。

#### find_free_tree 建製
根據 target size 大小決定要去左子樹或是右子樹，直到找到匹配的 size 大小。

if(target->size < (*root)->size)
{
    root = &(*root)->l;
}
else if(target->size > (*root)->size)
{
    root = &(*root)->r;
}

#### find_predecessor_free_tree建製
首先，需要透過迭代走到左子樹
再來並需找到左子樹中的最右節點。

block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
    block_t *pred = node->l;
    while (pred && pred->r)
    {
        pred = pred->r;
    }
    return pred;
}

#### insert_free_node 建製
透過比較 size 大小，決定該去左子樹或是右子樹，直到遇到`*root = NULL `節點，並且將新節點之就左右子樹 node 作清空。

void insert_free_tree(block_t **root, block_t *node) {
    while (*root) {
        if (node->size < (*root)->size)
            root = &(*root)->l;
        else
            root = &(*root)->r;
    }
    *root = node;
    node->l = node->r = NULL;
}

#### 參閱 memory-allocators

### 測驗3

## quiz2

### 測驗1
使用 Linux 核心風格 List API 的簡化標頭檔 list.h 來開發快速排序程式碼。

trace 之後，這個演算法以第一個 node 為 pivot:
1. 將 pivot 從原 list 移除。
2. 一次線性掃描把剩餘節點按照與 pivot 的大小關係移動至兩暫存 sublist （list_less 與 list_greater）

過程中，使用函式`list_move_tail`確保每個子串內部維持原先相對順序，掃描後，對兩個 sublist 遞迴呼叫同一函式完成排序，最後透過 `list_add`、`list_splice` 與 `list_splice_tail` 將「小於 pivot 的 sublist ＋ pivot ＋ 大於等於 pivot 的 sublist」重新串回原串位置。

#### 完善程式碼
* AAAA: `list_first_entry` 快速排序中，為了直接取第一個節點當 pivot。
* BBBB: `list_del` 把 pivot 從原 list 移除，避免跟其他元素混在一起。
* CCCC: `list_move_tail` 掃描原順序把 node 接到 sublist 尾端。(不使用`list_move`，否則順序反轉 )
* DDDD: `list_add` 目前 head 為空，把 pivot 放進去。
* EEEE: `list_splice` 把「小於 pivot」sublist 接到 head 前端（pivot 之前）。
* FFFF : `list_splice_tail` 把「大於 pivot」sublist 接到 head 尾端（pivot 之後）。

#### 解釋上方程式碼運作原理
流程如下:
1. 擷取 第一個 node 為 pivot，並且從主 list 中移除。
2. 一次線性掃描，以大小判斷剩餘節點並分組:
* 走訪剩餘節點，cmpint() < 0 → 丟到 `list_less` 尾端；否則丟到 `list_greater` 尾端。
* **丟**必須透過`list_move_tail`，才可保持原順序 (lab0作業犯過類似錯誤)
3. 遞迴排序兩個 sublist:
* list_quicksort(list_less)、list_quicksort(list_greater)。
4. 三組做拼接:
* 先把 pivot 接回 head，再把 `list_less splice` 到前面、`list_greater splice` 到尾端。

#### 為什麼 list_move_tail 不能換成 list_move
list_move() 把節點插到目標 list 的第一個元素之**前**
例如:
原本掃描順序:A→B→C
使用 `list_move`，內部順序變成 C→B→A，則無法滿足 stable sorting

### 測驗2

#### 觀察clz2

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

* 將 bits 切對半，分為 upper 以及 lower。
* e.g:
0000 0000 0000 0001 1111 0000 0000 0000
->
upper: 0000 0000 0000 0001
lower: 1111 0000 0000 0000
* 以遞迴方式開始計算 leading zero:
* 規則:
* 若 upper 等於 0，則下一次遞迴呼叫應檢查 lower 部分，並用計數器（counter）記錄目前已累計的 leading zero（等於 upper 位元數）。
* 若 upper 不等於 0，則下一次遞迴呼叫應繼續檢查 upper 部分。
* x : 要 check 的 32-bit 整數
* c : 遞迴的層數，以此決定切割位數(將 bits 切對半用的)
* mask[] = {0, 8, 12, GGGG}(不太了解):根據 code 是推導出 lower 的，且將 c 帶入推測其與遞迴有關:
1. 因此當 c 為 0，則 mask[0] = 0，也就是說 0x0000FFFF 不用做右移，與 x 做 AND 的話，upper被清零(變16bits)。
2. 當 c 為 1 則 mask[1] = 8，x此時已變成清0的lower值(16bits)，0x0000FFFF被右移 8bits，則變成 0x000000FF，與 x 做 AND ，upper被清零(變8bits)。
3. 當 c 為 2 則 mask[2] = 12，x此時已變成清0的lower值(8bits)，0xFFFF被右移 12bits，則變成 0x0000000F，與 x 做 AND ，upper被清零(變4bits)。
4. 當 c 為 3 則 mask[3] = GGGG，x此時已變成清0的lower值(4bits)，0xFFFF被右移 GGGG bits，則變成 ??，與 x 做 AND ，upper被清零(變??bits)。
* mask的作用就是找出 lower ?，當 c 等於3的時候，x 有4bits，而這4bits要分割為 2bits upper + 2bits lower，也就是有 2 bits的 lower 要分割，原本 lower 有16bits，因此16-14=2
* **GGGG**為 14。
* magic[] = {HHHH, 1, 0, IIII}(不太了解):推測在遞迴到某一程度時加入`if (c == JJJJ) `觸發magic。
1. lower最多16bits要取，因此變化如下:16, 8, 4, 2。
2. 最後lower只有2bits，lower 可能是十進位的 0、1、2、3，所以有可能是 2、1、0、0 的 lower leading zero。
3. 猜測magic只需要4個值的原因在於只需要遞迴4次，最後一次只需查詢 magic 即可知道 leading zero數量，不用再做 mask。
* **HHHH** : 2
* **IIII** : 0
* **JJJJ** : 3
* 當遞迴到一個階段觸發這段程式碼:

    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];

當遞迴到第3次，此時 x 有 4bits，upper為2bits、lower為2bits，此時有兩種情況:
1. upper非全0，此時查 magic 找 upper 的 leading zero數量(magic[upper] )。
2. upper全0，則必定有兩個 leading zero 了，因此可先加上去2接下來查 magic 找 lower 的leading zero數量 magic[lower]。
* **KKKK** : 2

* 遞迴結尾程式碼:

    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);

每次遞迴結尾，已經將x切半，判斷 upper 是否為0:
* upper ~~=~~ 0: 下一次遞迴進入`clz2(upper, c + 1)`。
* upper = 0: 前半bits皆為0，可以直接將0的數量加上去 `(16 >> (c))`，只須看lower部分 `clz2(lower, c + LLLL)`
* c只會往下一層走，因此為 c+1。
* **LLLL** : 1
#### 觀察clz64

static inline int clz64(uint64_t x)
{
    /* If the high 32 bits are nonzero, count within them.
     * Otherwise, count in the low 32 bits and add 32.
     */
    return (x >> 32) ? clz32((uint32_t) (x >> 32)) : clz32((uint32_t) x) + 32;
}

可以看出就是將 64bits再切扮成 32bits + 32bits的 upper+lower，兩種情況:
* upper 非 0 : 將其丟入 `clz32()`。
* upper 為 0 : 直接 加上32，並且做 lower 的 leading zero 確認。

#### 觀察 sqrti()
計算 64-bit 無符號整數的整數平方根
##### 初始條件判斷

if (x <= 1)
        return x;

平方根 0 = 0
平方根 1 = 1
##### 開始做平方根

int shift = (total_bits - 1 - clz64(x)) & MMMM;
m = 1ULL << shift;

**如果將開根號以二進位觀察，則是將2bits算一格**，例如:
4 = 0010 -> 將2bits算一格 -> 01 -> 2
**而 2bits 為 4的冪**
假如 x = 50， clz64(50) = 58，shift = (64 - 1 - 58) & MMMM = `5 & MMMM`
既然需要是4的冪，則不能有奇數次方，將第一位bit削掉，就是 5 & 111...10 = 5 & ~1
**m** = `1 << (5 & ~1)` (做向左移位) = 1 << 4 = 16、**x** = 50、**y** = 0
進入迴圈第0次:

1. **b** = 0 + 16 = 16
2. `y >>= NNNN `:已確定的根左移一欄，空出下一位。故 **NNNN** = 1， y = 0
3. 50 >= 16 -> true -> 進入 `if (x >= b)`
4. **x** -= b -> x = 50 - 16 = 34
5. **y** += m -> **y** = 16
6. **m** >>= PPPP = 4，將2bits算一格，也就是說此次遞迴做完2bits，故往右走2bits，**PPPP** = 2。
7. **(x , y , m)** = (34, 16, 4)

進入迴圈第1次:
.....**(x , y , m)** = (14, 12, 1)
進入迴圈第2次:
.....**(x , y , m)** = (1, 7, 0)
m 為 0 跳出，得到答案 y = 7。

> b = y + m 的意義是什麼?

**m :**
* 從最高位元，每次處理2bits的一組數值後往下2bits處理，類似掃描。

**x :**
* 一開始是輸入的整數 x
* 隨著每次確認好**根bits**後，就會更新。
* 表「剩下可以讓平方根繼續加的量」。

**b :**
`b = y + m;` ，也就是類似一個預測目前算好的根bits加上下一組要處理的bits時，是否會有問題。

if (x >= b) {
    x -= b;
    y += m;
}

進入比較，看剩下的 x 值是否夠放得下這些位元，如果夠就可以留下來。

**y :**
是目前處理完的累積下來的根，也是最後的解答。

#### 擴充為向上取整數實作

#### 不依賴除法指令的 sqrtf

#### 「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

### 測驗3

#### map_init()
基本建立 hash_table。

配置記憶體空間，為 map_t 結構大小:

map_t *m = malloc(sizeof *m);

map_t結構:

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

存入得到的bits，bits 決定雜湊表大小：bucket 數量為 2^bits。

m->bits = bits;

配置 bucket 陣列:

m->ht = calloc(MAP_HASH_SIZE(bits), sizeof(struct hlist_head));

* 使用 calloc的原因，根據C99規格書中，關於`calloc()`函式:
> 7.20.3.2 The free function
> The calloc function allocates space for an array of nmemb objects, each of whose size
is size. The space is initialized to all bits zero.

推測是為了讓所有 bucket 初始為 0 bits。

* `MAP_HASH_SIZE(bits) `是一個巨集，定義為：

    #define MAP_HASH_SIZE(bits) (1u << (bits))

也就是設置 2^bits 個 bucket。
* 每個 bucket 是 `struct hlist_head`，也就是原始碼中 type.h:

    struct hlist_head {
        struct hlist_node *first;
    };

* 初始化 table 完成後，回傳指向這張 map 的指標。

#### map_add()
插入 key→data

* `if (find_key(m, key)) return; ` : 防止覆蓋
* 存入 data (陣列位置) 以及 key (值)
* `struct hlist_head *h = &map->ht[hash(key, BBBB)];` : 需要知道 map 到哪一個 bucket，而 table 是透過 bits 做建構，因此需要的是 bits，故 **BBBB** = `map->bits` 。

    n->next = first;
    if (first)
        CCCC = &n->next;

* 目前這個 bucket 的第一個節點是 `first`。
* 將新的 node 插入最前面，則first變成舊的，也就是`n->next`，則也要更新 prev，因此 **CCCC** = `first->pprev`。

    h->first = n;
    DDDD = &h->first;

* 當 n 成為 bucket 的第一個節點，它的 pprev 就該指向 bucket 本身的 first 欄位。
* **DDDD** = n->pprev

#### map_deinit()
目的應該是釋放整個 hash_table 的記憶體。

**掃描每個 bucket :**

for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
    struct hlist_head *head = &map->ht[i];

* hash_table 是一組 bucket 陣列，而每個 bucket 是一條 hlist 的 list。
* ` i < MAP_HASH_SIZE(map->bits)` : 也就是從 0 到 2^bits - 1 ，每個 bucket 逐次整理。
* `map->ht[i]` 就是一條單向鏈(`struct hlist_head`)的起點。

**掃描此 bucket 的 hlist :**

for (struct hlist_node *p = head->first; p;) {     struct hash_key *kn = container_of(p, struct hash_key, node);
    struct hlist_node *n = p;
    p = p->next;

* 目的 : 進入 bucket 後，開始掃描此 bucket 的 hlist。
* 利用 `container_of() `巨集從 node 指回 paerent 結構。
> 巨集 container_of 則在 offsetof 的基礎上，擴充為「給定成員的位址、struct 的型態，及成員的名稱，傳回此 struct 的位址」

* parent 結構:

    struct hash_key {
        int key;
        void *data;
        struct hlist_node node;
    };

* 透過 node 就能知道整個 kn 結構。

**移除節點前置 :**

struct hlist_node *next = n->next, **pprev = EEEE;

* 推測是為了輔助知道目前要釋放的 bucket 的位置，可以以此推斷是在中間或是開頭。
* `pprev` 是「指向上一個節點的 `next` 欄位」的位址
* 因此 **EEEE** = n->pprev

**開始移除節點 :**

*pprev = next;
if (next)
    next->pprev = pprev;

* 修改目前節點的前一節點的 data 值為目前節點的下一 node。

**清除資料，釋放記憶體 :**

bail:
    free(kn->data);
    free(kn);
free(map);

#### two_sum()

map_t *map = map_init(10);
*returnSize = 0;
int *ret = malloc(sizeof(int) * 2);
if (!ret)
    goto bail;

* 設置 10 bits，也就是 2^10 = 1024 個 bucket。
* `target`，要湊出的目標和。
* `returnSize`，答案陣列的長度，預設為 0。
* 先設置好 malloc `ret` 存回傳結果。

for (int i = 0; i < numsSize; i++){
...
}

* 進入迴圈開始掃描湊數字和為 `target`。
* 根據測驗3說明，如果 `target` 是 a + b，那麼只要曾經看過 a，現在出現 b 就能湊對。

int *p = map_get(map, target - nums[i]);

其中 `target - nums[i]`:
* 確認扣除已經掃描的部分，還剩下的數值。
* 例如，看到第 i 的數，則要與目前的數字 a 湊對的話，需要掃描 a 之後，也就是 target - nums[i]。

則整段程式碼就是，以 map_get 查表，查`target - nums[i]`

1. 假如查到了:

    if (p) { /* found */
                ret[0] = i, ret[1] = *p;
                *returnSize = 2;
                break;
            }

* 代表第 i 個數就是我們所求湊對，將 `ret[0] = i`，以及之前查到遇過的值`*p`，設置`ret[1] = *p`

2. 假如沒查到:

    p = malloc(sizeof(int));
    *p = i;
    map_add(map, nums[i], p);

* 把現在這個數字(`nums[i]`)的索引裝進指標裡，加入 hash_table。