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 whentest_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.

Todo
Implement "merge sort" based on test 1.

Test 2

remove_free_tree

To understand this code in a short time, take a look atremove_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.

To do:

• complete functions
• Test the functionalities and performace