# 2025q1 Homework2 (quiz1+2)
contributed by < vicLin8712 >

## QUIZ `1`
### Test `1`
#### `my_run_test`
Observe the `main` function; it is called the `test_suit` function on the second line. Consider the macro `my_run_test`, which is embedded in the function `test_suit`. I found that the parameter to it is the pointer to `test_list.` Replace `test` with `list_test` to observe, the code of which is shown below.

#define my_run_test(test_list)       \
    do {                             \
        char *message = test_list(); \
        tests_run++;                 \
        if (message)                 \
            return message;          \
    } while (0)

This code repeats `test_list` until it returns when`test_list` doesn't return null pointer.

#### `test_list`
In `test_list`, this function reset list by function `list_reset`.
Structure `list_item_t` in `list_reset` function, member `value` set to the integer `i` of i-th order in the list and the `next` point to null.

Next, inserting initialized node at the begining. The following code shows how it works.

for (size_t i = 0; i < N; i++)
        list_insert_before(&l, l.head, &items[i]);

Now consider how function `list_insert_before` is implemented.

atatic inline void list_inset_before(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;
}

`for` loop here is used to move the pointer `p` point to the address of the pointer, which should be inserted new item. Starting from the list head, `AAAA=&l->head`, moving until `BBBB=before`, with step `p=&(*p)->next`.
Now `p` is a pointer to the address of the pointer point to which should be inserted `list_item_t *item`.
After that, connect with `before` which is inserted a new `list_item_t` before. Below are diagrams to illustrate this function clearly.

* Loop starts
Initial state as picture show
* Iteration
* Until `*p == before`
* Insert `new_item`
* `new_item.next` connect to `before`

Next, another loop will be progressed to check whether the list builds correctly by checking the value of each element that has been assigned in the above insertion process.
After all tests are processed, `test_list` return `NULL` and assigned to the parameter `message` to check whether `test_list` executed successfully.
In the end, return `NULL` to the parameter `result` in the main function.
Worthy to note is that the return value `!!result` ensures the return value to be `1` or `0`.
> [color=#ddd018]Todo
> Implement "merge sort" based on test `1`.
### Test `2`
#### `remove_free_tree`
To understand this code in a short time, take a look at`remove_free_tree` function.

First, we encounter the following code

 block_t **node_ptr = find_free_tree(root, target);

Go back to check the function `find_free_tree`; however, it is just a prototype. I guess it can return an address of a pointer that points to the `target,` the parameter to `find_free_tree,` which might exist under the tree with root `root.`

Continue with the following code.

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;

This condiction branch handle the situation that target node has two childre. As the comment, this while loop is trying to find the rightmost node in the left subtree. We have: `EEEE = (*pred_ptr)->r` and `FFFF = &(*pred_ptr->r)`. Below diagrams show the prcess.
* Initial State
The `pred_ptr` points to `&(*node_ptr)->l`.

* Find the rightmost node

Then, the following code tries to confirm the result of a rightmost node in the left subtree.

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

When the predecessor node is found, we will replace the target with it and maintain all structures simultaneously.

Consider the situation if the predecessor is the immediate left child. It means that we can move right subtree of target to the right subtree of left node of target.

If the predecessor is deeper in the left subtree, we call `remove_free_tree` function again to remove predecessor. Consider the following code.

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);
}

As `find_free_tree` discussed above, `node_ptr` is the same as the address of pointer, `target`. As picture shown below.

In `remove_free_tree(&old_left, *pred_ptr)` function, branch will jump to the codiction codes as one of below code because `(*node_ptr)->r = NULL` and `(*node_ptr)->l` perhaps exist.

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;
    }

Now will obtain the predecessor node removed with no children from the tree and can replace `256` with it.

> [color=#ddd018] To do:
> * complete functions
> * Test the functionalities and performace