# 2024q1 Homework2 (quiz1+2)
contributed by < `williamlin0518` >

## [第一週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)

### 測驗一

:::danger
不用列出參考題解，專注於程式碼行為分析和你的改進。
:::

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA);
    return *left;
}

`left = &(*left)->next;`

`(*left)->next`: Accesses the next pointer of the current node.

`&(*left)->next`: Takes the address of the next pointer of the current node, which is then assigned to left for the next iteration.

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB);
    }
    return n;
}

`left = &(*left)->next;`

Similar to `list_tail`, it takes a pointer to a pointer to the first node of the list as its parameter.

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = CCCC;
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = DDDD;
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = EEEE;

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

`CCCC` : p->next
`DDDD` : `list_tail(&left)` should be the last node of the left list
`EEEE` : `list_tail(&right)` should be the last node of the right list

Given the list: 4 -> 2 -> 6 -> 1 -> 3 -> 5, we choose the first element as the pivot for simplicity

digraph G {
    rankdir=LR;
    pivot [label="pivot" shape=plaintext];
    NULL [shape=none];
    
    4 -> 2 -> 6 -> 1 -> 3 -> 5 -> NULL;
    { rank=same; pivot -> 4; }
}

After partitioning, our lists are:
1. Left List: 3 -> 1 -> 2
2. pivot: 4
3. Right List: 5 -> 6

digraph G {
    node [shape=record];
    rankdir=LR;
    
    
    
    subgraph cluster_right {
        label = "Right of Pivot";
        color = green;
        n3_2 [label="5"];
        n6_2 [label="6"];
        n3_2 -> n6_2;
    }
    
    subgraph cluster_pivot{
        label = "Pivot (4)";
        n1_2 [label="4"];
    }
    
    subgraph cluster_left {
        label = "Left of Pivot";
        color = blue;
        n2_2 [label="3"];
        n4_2 [label="1"];
        n5_2 [label="2"];
        n2_2 -> n4_2;
        n4_2 -> n5_2;
    }

    

    n1 [label="4"];
    n2 [label="2"];
    n3 [label="6"];
    n4 [label="1"];
    n5 [label="3"];
    n6 [label="5"];
    n1 -> n2;
    n2 -> n3;
    n3 -> n4;
    n4 -> n5;
    n5 -> n6;

    
}

After sorting each partition, we need to concatenate them in order:

1. Concatenate the sorted left list with the pivot.
2. Concatenate the result of step 1 with the sorted right list.

### 測驗二

#### Timsort

Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

#### Minimum Run Size:

If a run is smaller than this minimum size, Timsort will perform an insertion sort on this run and possibly adjacent elements to meets the minimum size.

#### AAAA

`struct list_head **tail = &head;
`
AAAA should be initialized to point to the head of the merged list. Since tail is used to track the end of the merged list as it's being built

#### BBBB and CCCC - Updating tail in merge function
`tail = &(*tail)->next;`
Both BBBB and CCCC are involved in updating the tail pointer after adding either a or b to the merged list.
#### DDDD and EEEE - Final links to make a circular doubly-linked list in build_prev_link

DDDD :`tail->next`
EEEE :`head->prev`
#### FFFF
less than or equal to 1 : direct build links

if (stk_size <= 1) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);

### Timsort Steps

Let's illustrate the steps with a simple example. Consider a list: 5 -> 3 -> 4 -> 1 -> 2.

digraph G {
    rankdir=LR;
    NULL [shape=none];
    
    5 -> 3 -> 4 -> 1 -> 2 -> NULL;
    
}

#### Finding Runs:

Initially, we identify runs in the list. Single elements are considered runs of length 1.
For our example, each element might be its own run since there's no clear ascending or descending order.

#### Merging Runs:

Based on run_size, we decide whether to merge adjacent runs. The decision is based on the lengths of the runs, aiming to merge smaller runs first to maintain stability and efficiency.

1. Merge 5 and 3 to get 3 -> 5.
2. Merge 4 into the existing run to maintain order: 3 -> 4 -> 5.
3. Merge 1 and 2, then merge that run into the existing sorted list: 1 -> 2 -> 3 -> 4 -> 5.

## 第二週測驗題

### 測驗一
using the preorder array to determine root nodes and the inorder array to distinguish between left and right subtrees
#### AAAA
`"AAAA" : n->next = h->first;`
assigns the new head's next pointer in the hlist_add_head function.

#### BBBB
`BBBB" : &heads[hash]`
when iterates over the list starting from the head, pointing to the correct bucket in the hash table to search for the value.
#### CCCC
`list_entry`
function that converts a list pointer to the enclosing structure.
list_entry: convert a pointer to struct hlist_node back into a pointer to the containing struct order_node.

#### DDDD

`&heads[hash]`
adding nodes to a hash table, should be the head of the correct bucket

#### Explanation
example to illustrate how buildTree works:

Preorder: [3, 9, 20, 15, 7]
Inorder: [9, 3, 15, 20, 7]

1. Looking into the inorder array, 9 is on the left side of 3, and 15, 20, 7 are on the right side, indicating that 9 is part of the left subtree, and 15, 20, 7 form the right subtree.
2. For the right subtree, the root is 20 (the next element in the preorder array after 3 and 9), with its inorder traversal being [15, 20, 7].
3. repeats recursively, splitting the tree into smaller subtrees and reconstructing them until the entire binary tree be formed.
### 測驗二
#### LRU (Least Recently Used) cache
1. utilizes a combination of doubly linked lists and hash tables to achieve efficient O(1) operations for access and update.
2. `struct hlist_node` : includes not only a pointer to the next node (next) but also a pointer to the previous node's next pointer (pprev). This design allows for constant-time removal of the node from the list without traverseing the list to find the predecessor node
#### EEEE
EEEE: In the hlist_del function, this should be next->pprev. It is meant to update the pprev pointer of the next node in the list to point to the previous node's pprev pointer
#### FFFF
FFFF: In the lRUCacheFree function, this should be link, which is the member of LRUNode that is used to link nodes in the doubly linked list.
#### GGGG
&cache->link, the pointer to the link field within the LRUNode structure, indicating the node to be removed from the list.
#### HHHH
HHH: In the lRUCacheGet function, this should be node, indicating the specific member within the LRUNode structure that is being used to navigate through the hash list.
#### IIII
IIII: In the lRUCacheGet function, calling list_move, it should be &cache->link, pointing to the link field within the LRUNode structure, indicating the node to be moved to the head of the list for LRU caching purposes.
#### JJJJ
within the hlist_for_each loop, this should also be node, as it refers to the member used to iterate through nodes in the hash list.
#### KKKK
&c->link: indicating the specific node's position in the doubly linked list to be updated.
### 測驗三

finding set bits (bits with value 1) within a large array of bits

static inline unsigned long find_nth_bit(const unsigned long *addr,
                                           unsigned long size,
                                           unsigned long n)
{
    if (n >= size)
        return size;

    if (small_const_nbits(size)) {
        unsigned long val = *addr & GENMASK(size - 1, 0);

        return val ? fns(val, n) : size;
    }

    return FIND_NTH_BIT(addr[idx], size, n);
}

1. If n is greater or equal to size, it means the requested set bit does not exist within the given size, so it returns size as an indication that the bit was not found.

2. `FIND_NTH_BIT` macro is used for larger bitmaps. It iterates over each word in the bitmap:
a. If current word contains more than n set bits, finding the exact position of the Nth set bit within this word using `fns`.