# 2025q1 Homework2 (quiz1+2)
contributed by < horseface1110 >
## quiz1_1
完成list_insert_before 函式

{
    list_item_t **p;
    for (p = &l->head; *p != before; p = &(*p)->next)
        ;
    *p = item;
    (*p)->next = before;
}

#### for迴圈：尋找要插入的節點位置
- 初始化：先將p設為指向head這個指標的指標
- 尋找插入點：因為p是指標的指標，每次判斷他指向的指標是否為目標，不是的話，就指向下個節點的指標。
#### 為甚麼要用pointer to pointer：
如果只用pointer的話，遇到插在投的話需用判斷條件
### 合併排序操作
## quiz1_2
完成填空部分

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

提問：已經有function可以找中序前行節點了，為甚麼還要自己找(未解)

block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
assert(expected_pred == *pred_ptr);

運作邏輯：
這段程式碼主要在找可以分配出去的空間，整個空間用樹狀結構表示，所以當找到可以分配出去的節點時，選擇使用中序前行節點置入被移除的節點的位置。
有幾種狀況：
- 目標節點有左右子
- 先找出中序前行節點：
- 是直接左子節點：
- 在左子樹的深處
- 目標只有一個子節點
- 子節點直接取代
- 目標沒有子節點
- 直接刪除

填空部分的目標是找到中序前行節點以取代要被刪除的節點位置，使用了pointer to pointer，指向一個指標，每次檢查他指向的指標指向的節點是否有右子，如果沒有，那現在指向的就是目標節點。
**為甚麼用pointer to pointer？**
如果使用`*pred`的話，追蹤到目標節點時，會不知道是誰指向他，沒辦法將該點自樹中移除
如果使用`**pred`的話，因為指標指向的是**指向該節點的指標本身**，可以直接修改

## quiz1_3

static void rebuild_list_link(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *prev;
    prev = head;
    node = head->next;
    while (node) {
        node->prev = prev;
        prev = node;
        node = node->next;
    }
    prev->next = head;
    /* GGGG */;
    head->prev = prev
}

這邊依照`list.h`的linklist來說，是雙向環狀串列，所以我認為`GGGG`毫無懸念的是將head的prev指向尾巴，但我不知道為甚麼是錯的(未解)

....
if (L != R) {
    struct list_head *pivot = L;
    value =  list_entry(pivot,node_t,list)->value
    struct list_head *p = pivot->next;
    pivot->next = NULL; /* break the list */

這段程式碼要找出pivot的值，用來比較，所以用list.h中定義的`list_entry`取出數值之後，存在`value`。
提問：break the list時，不需要將p的prev也清掉嗎？(未解)

struct list_head *n = p;
p = p->next;
int n_value =  list_entry(n,node_t,list)->value/* IIII */;
if (n_value > value) {
    n->next = right;
    right = n;
} else {
    n->next = left;
    left = n;
}

跟pivot，若節點的值 > pivot，就被分去`right`串列之中，所以`IIII`是`list_entry(n,node_t,list)->value`取出節點`n`之值

begin[i] = left;
begin[i + 1] = pivot /* JJJJ */;
begin[i + 2] = right /* KKKK */;

最後會將原linklist分為三個部分：`left`、`pivot`、`right`，所以最後填入`pivot`、`right`毫無懸念
#### 程式碼運作原理：
**概述**：
- `pivot`：將linklist左右畫分的節點
- `left`：數值小於等於pivot的節點的linklist
- `right`：數值大於pivot的節點的linklist
- `begin`：堆疊，紀錄要被排序的linklist的head

用`pivot`將linklist分成三部分，每次都先處理`right`這份，處理完後接到`pivot`後面，再處理`left`，最後再全部接起來
**圖解**：
初始linklist(為求畫面美觀，先省略`prev`指標和結尾`NULL`)
目前`pivot`是42，第一次`while`後：
第二次`while`後：
**為什麼begin大小為2 * n？：**
因為在最糟情況下(遞增或遞減)，串列在每次分割時都只會集中在left/right和一個節點的pivot。依照程式碼，處理一個串列時，在beign[]上就好像該點解壓縮一樣，一個點變三個點，也就是說，每次處理時，額外增加兩個資料。理論上：共需要分割n-1次，所以會有2(n-1)個新的資料點產生
但實際上，left、right之中一定會有一個NULL，在執行過程中，right是NULL的話會被忽略，不會長期的占用空間，所以實際上不會真的用到2(n-1)+1個格子。(第三、四步驟)

## quiz2_1
### 邏輯概述：
先取出linklist的第一個點當`pivot`，接著比較，小於`pivot`就串到`list_less`，否則串到`list_greater`，遞迴處理`list_less`、`list_greater`之後，再串在一起
### 填空部分：

pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);

這邊要先把linklist第一個元素取出來當pivot，所以填入`list_first_entry`。再來要把pivot節點從排序的list中移除，所以用`list_del`。

list_for_each_entry_safe (item, is, head, list) {
    if (cmpint(&item->i, &pivot->i) < 0)
        list_move_tail(&item->list, &list_less);
    else
        list_move_tail(&item->list, &list_greater);
}

這邊就是把比較完之後的節點放到各自的位置而已。
**為什麼是`list_move_tail`而不是`list_move`**：
用 `list_move_tail()` 是因為我們想要讓排序是穩定的。假設有兩個值一樣的節點 A 跟 A'，原本 A 在前面，我們就希望排序後它們還是這個順序。如果用 `list_move()`把新的節點插在 list 開頭，就會讓順序顛倒。所以我們用 `move_tail()`把符合條件的節點依序加到尾巴，保持原本的順序。

list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);

這段要將排序好的串列們接在一起
`list_add`是將一個節點接到另一點後方，這邊先將pivot接到head後面。
接著要把`list_less`放在pivot前面，由於是一整個串列的移動，所以用`list_splice`將整個串列插在head後面，pivot前面。最後要將`list_greater`放到pivot後面，所以用`list_splice_tail`插在整個串列的尾端
## quiz2_2
- 首先，我們需要知道clz2要得到什麼資訊：前導0的個數
- 邏輯概述：先檢查上半部，再換到下半部，如果上半部全零，下次檢查下半部；如果上半部不全零，下次檢查下半部，直到檢查部分是2bit。
程式碼填空

static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};

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 == 3)
        return upper ? magic[upper] : 2 + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

最一開始clz2的參數`c`由0開始。
**第9行**`：uint32_t upper = (x >> (16 >> c));`，表示這次要檢查的部分，`16>>c`意思是$\frac{16}{2^c}$，例如c = 0時，upper = x向右位移16bit，也就是upper = 高位16bit的意思。
**第11行**：`c == 3`，進入遞迴停止的條件是檢查的bit數為2時，而當c == 3 時，表示upper已經只有2 bit。
**第12行**：若upper = 0，則表示lower前面2 bit都是0，所以前導0個數+2，故這邊為2 + magic[lower]
**第13行**：每次檢查的精度*2，所以c+1
## quiz2_3

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next, **pprev;
};

這段程式碼非常神奇，剛看到有點疑惑，所以在這邊紀錄：
`struct`裡面怎麼又包了自己呢？
[規格書 6.2.5 - 22](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
>A structure or union type of unknown content (as described in 6.7.2.3) is an incomplete type. It is completed, for all declarations of that type, by declaring the same structure or union tag with its defining content later in the same scope.
>
這段是說：struct裡面不能有自己的實例，但可以有自己的指標，因為指標大小事已知的。
一開始疑惑的點是：「可以這樣包？這甚麼寫法」後來想到常見的含指標的node裡面也是這樣寫的。

static struct hash_key *find_key(map_t *map, int key)
{
    struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
    for (struct hlist_node *p = head->first; p; p = p->next) {
        struct hash_key *kn = container_of(p, struct hash_key, node);
        if (kn->key == key)
            return kn;
    }
    return NULL;
}

邏輯概述：目標找到hash表中的特定key，所以要先取得hash後的bucket值，接著在該bucket中尋找該key。
所以第三行`AAAA`應該要填：`map->bit`。

void map_add(map_t *map, int key, void *data)
{
    struct hash_key *kn = find_key(map, key);
    if (kn)
        return;

    kn = malloc(sizeof(struct hash_key));
    kn->key = key, kn->data = data;

    struct hlist_head *h = &map->ht[hash(key, BBBB)];
    struct hlist_node *n = &kn->node, *first = h->first;

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

邏輯概述：要把新的節點插在bucket的第一個。先創好節點後填入數據，再將該節點插到bucket的第一格。
`h`：該節點要被分配到的bucket
`n`：指向要插入的節點的指標
`first`：該bucket目前第一個節點的指標
所以`BBBB`應該填入：map->bit，當作取得hash值的參數。

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

如果該bucket中已經有節點的話，`if`成立，要把新節點插入bucket的頭，所以`CCCC`填`first->pprev`，將原第一節點的往前指標指向`&n->next`
最後將`n->pprev`指向`h->first`，以上這段就是在將新節點n插入bucket的頭部的過程。

void map_deinit(map_t *map)
{
    if (!map)
        return;

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

            if (!n->pprev) /* unhashed */
                goto bail;

            struct hlist_node *next = n->next, **pprev = EEEE;
            *pprev = next;
            if (next)
                next->pprev = pprev;
            n->next = NULL, n->pprev = NULL;

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

邏輯概述：這段程式碼目標是移除一個節點，並保持串列結構正常。所以選定移除的節點之後，把與他相關的指標處理好。

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

當要移除節點 n 時，會先取得它的下一個節點 next，並透過 n->pprev 這個 pointer to pointer 取得前一個節點中指向自己的指標位置，因此 EEEE 應填入 n->pprev。接著將 *pprev 設為 next，斷開目前節點與前一節點的連結；若 next 存在，則更新 next->pprev 指向原本的 pprev，讓其指向前一個節點指向自己這個節點的指標記憶體位址。最後將 n 的指標清空，並釋放該節點，即可正確地將節點從鏈結串列中移除，並保持整體結構的完整。