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

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

#### Observations
What we care about is what to fill in `AAAA` to `DDDD`, which are all in the the function of `list_insert_before`. So we could ignore how testing is done.

We only focus on:
- implementation of `list_insert_before`

{
    list_item_t **p;
    for (p = AAAA; *p != BBBB; p = CCCC)
        ;
    *p = item;
    DDDD = before;
}

- document of the function

- definition of `list_item_t`, `list_t`

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

typedef struct {
    struct list_item *head;
} list_t;

So the list would look like this:

#### Solve
The document says
> *This function traverses the list to locate the position immediately before the item pointed to by @before and inserts @item in that position.*

and by looking at the code, we could intuitively know that:
- `AAAA` is the indirect pointer of the first element in the list
- `CCCC` is the next element's indirect pointer

which are `&l->head` and `&(*p)->next` respectively.

To determine the value of `BBBB`, the statement after the loop `*p = item` assigns `item` to value of `p`, which means it's connecting a certain node to `*item`. In this case, the node should be the node before `*before`. If the next node is `*before`, `*p` would be `before`. Therefore, the answer for `BBBB` is `before`.

Finally, we should connect `*item`'s next to `before`, so `DDDD` should be `(*p)->next`.

#### Answer
`AAAA`: `&l->head`
`BBBB`: `before`
`CCCC`: `&(*p)->next`
`DDDD`: `(*p)->next`

---

### [Q2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2)

---

### [Q3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3)

#### Solve
Looking at `rebuild_list_link`, we could guess that this function should probably make sure all nodes inside the list have `next` and `prev` pointers set properly.
The while loop inside the function:

 while (node) {
    node->prev = prev;
    prev = node;
    node = node->next;
}

Links the current `node`'s `prev` pointer to the previous node.
And outside the loop:

prev->next = head;
/* GGGG */;

the last node's `next` is linked to the first node, so `GGGG` should link the first node's `prev` to the last node. Therefore, it should be `head->prev = prev`.

The rest of the fields to fill are all in the implementation of `quick_sort` using Linux style linked list.

struct list_head *pivot = L;
value = /* HHHH */

Looking back to the original version,

node_t *pivot = L;
value = pivot->value;

we can see that it should be the pivot's value. Using Linux style list, we can get the address of the struct that `list_head` is in by calling `list_entry(pivot, node_t, list)` and get its value by `list_entry(pivot, node_t, list)->value`.

Same for `n_value`:

int n_value = /* IIII */;

we can get its value by `list_entry(n,node_t,list)->value`

Finally,

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

comparing to the original version:

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

for index `i` ~ `i+2` it should be `left`, `pivot`, `right`.

#### Answer:
`GGGG`: `head->prev=prev`
`HHHH`: `list_entry(pivot,node_t,list)->value`
`IIII`: `list_entry(n,node_t,list)->value`
`JJJJ`: `pivot`
`KKKK`: `right`

## 第二週測驗
### [Q1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1)
According to last week's Q3, we know how to perform quick sort on linked list.

INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

pivot = AAAA(head, struct listitem, list);
BBBB(&pivot->list);

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

list_quicksort(&list_less);
list_quicksort(&list_greater);

DDDD(&pivot->list, head);
EEEE(&list_less, head);
FFFF(&list_greater, head);

The pivot should be first entry of the list, therefore, `AAAA` should be `list_first_entry`.

Then, we need to iterate the list entries and move the nodes to different lists based on whether its value is larger or smaller than pivot.
Deleting the pivot from the list first allows us to use `list_for_each_entry_safe` more conveniently. So `BBBB` should be `list_del`.

After comparison, the nodes should move to the *tail* of `list_less` or `list_greater`. This ensures that the sorting is **stable**. So `CCCC` should be `list_move_tail`.

Then, perform quick sort on `list_less` and `list_greater`.

Finally, we should move the nodes back to original list `head`. We first add `pivot` back to the list using `list_add`, then use `list_splice` to move `list_less` to beginning of `head` and `list_splice_tail` to move `list_greater` to end of `head`.

#### Answer:
`AAAA`: `list_first_entry`
`BBBB`: `list_del`
`CCCC`: `list_move_tail`
`DDDD`: `list_add`
`EEEE`: `list_splice`
`FFFF`: `list_splice_tail`

### [Q2](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-2)
### [Q3](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-3)