# 2025q1 Homework2 (quiz1+2)

contributed by < `NeedToDebugMyLife` >

## [Quiz 1](https://hackmd.io/@sysprog/linux2025-quiz1)
### `Q1`
#### 資料結構


1. `list_item_t`

    typedef struct list_item {
        int value;
        struct list_item *next;
    } list_item_t;

2. `list_t`

    typedef struct {
        struct list_item *head;
    } list_t;

#### 題目

static inline void list_insert_brfore(list_t *l, list_item_t *before, list_item_t *item)
{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

#### 答案
* `AAAA` = `&l->head`
* `BBBB` = `before`
* `CCCC` = `&(*p)->next`
* `DDDD` = `item->next`

#### 說明
此段程式用於插入一個新節點到目標節點的前方
* `for` 迴圈用於走訪佇列來找出要插入的位置
* 找到後將節點插入到該位置 (`*p = item`)
* 將新節點的 `next` 指標指向 `before` 節點
<br>

**<font size=4>Case1</font>** - 考慮將節點 3 (`item`) 插入到佇列 (`l`) 的節點 4 (`before`) 前:
##### 初始狀態

:::info
* `l` 是指向 "**`list_t` 結構**" 的指標
* `p` 是指向 "**`list_t` 結構內的 `list_item` 指標**" 的間接指標
* `*p` 是指向 "**`list_t` 結構內的 `list_item` 指標"** 所指向的 "**`list_item` 結構**"<small>(AAAA)</small>
* `before` 是指向 `list_item_t` 結構的指標，用於表示插入位置節點<small>(4)</small>
* `item` 是指向 `list_item_t` 結構的指標，用於要插入的節點<small>(3)</small>
:::

指標 `p` 用於走訪節點，每次檢查節點完成後都會往後移動一節點<small>(CCCC)</small>，當 `*p` 指向 `before` 節點時<small>(BBBB)</small>，結束走訪
##### 走訪輪數1

##### 走訪輪數2
`*p` 指向 `before`, 結束走訪。此時 `p` 指向節點 2。

##### 插入節點
將 `item` 插入到 `p` 後方 <small>(即 `*p`指向的位置)</small>

將 `item` 節點的 `next` 指標指向 `before` 節點 <small>(DDDD)</small>
完成插入
<br>

**<font size=4>Case2</font>** - 考慮將節點 1 (`item`) 插入到佇列 (`l`) 的節點 2 (`before`) 前:
##### 初始狀態
因為 `*p` 指向 `before`, 所以不需要走訪。此時 `p` 指向 `head` 節點 (`&l->head`)。

##### 插入節點
將 `item` 插入到 `p` 後方 <small>(即 `*p`指向的位置)</small>

將 `item` 節點的 `next` 指標指向 `before` 節點 <small>(DDDD)</small>
完成插入

:::success
可以發現使用間接指標插入節點的方式，無論在哪一種情況下，`l` 指標都是不需要更動的。
:::
<br>

### `Q2`
#### 資料結構
1. `block_t`

    typedef struct block {
        size_t size;
        struct block *l, *r;
    } block_t;

<br>

#### 題目

void remove_free_tree(block_t **root, block_t *target)
{
    /* Locate the pointer to the target node in the tree. */
    block_t **node_ptr = find_free_tree(root, target);

    /* If the target node has two children, we need to find a replacement. */
    if ((*node_ptr)->l && (*node_ptr)->r) {
        /* Find the in-order predecessor:
         * This is the rightmost node in the left subtree.
         */
        block_t **pred_ptr = &(*node_ptr)->l;
        while (EEEE)
            pred_ptr = FFFF;

        /* Verify the found predecessor using a helper function (for debugging).
         */
        block_t *expected_pred = find_predecessor_free_tree(root, *node_ptr);
        assert(expected_pred == *pred_ptr);

        /* If the predecessor is the immediate left child. */
        if (*pred_ptr == (*node_ptr)->l) {
            block_t *old_right = (*node_ptr)->r;
            *node_ptr = *pred_ptr; /* Replace target with its left child. */
            (*node_ptr)->r = old_right; /* Attach the original right subtree. */
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        } else {
            /* The predecessor is deeper in the left subtree. */
            block_t *old_left = (*node_ptr)->l;
            block_t *old_right = (*node_ptr)->r;
            block_t *pred_node = *pred_ptr;
            /* Remove the predecessor from its original location. */
            remove_free_tree(&old_left, *pred_ptr);
            /* Replace the target node with the predecessor. */
            *node_ptr = pred_node;
            (*node_ptr)->l = old_left;
            (*node_ptr)->r = old_right;
            assert(*node_ptr != (*node_ptr)->l);
            assert(*node_ptr != (*node_ptr)->r);
        }
    }
    /* If the target node has one child (or none), simply splice it out. */
    else if ((*node_ptr)->l || (*node_ptr)->r) {
        block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
        *node_ptr = child;
    } else {
        /* No children: remove the node. */
        *node_ptr = NULL;
    }

    /* Clear the removed node's child pointers to avoid dangling references. */
    target->l = NULL;
    target->r = NULL;
}

#### 答案
* `EEEE` = `(*pred_ptr)->r`
* `FFFF` = `&(*pred_ptr)->r`

#### 說明
此段程式用於管理可使用的記憶體區塊

**<font size=4>Case1</font>** - 考慮釋出一可用空間 `r`