2025q1 Homework2 (quiz1+2)

contributed by < SimonLiu423 >

第一週測驗

Q1

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

---

Q3

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

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

Q3