---
tags: linux2023
---
# 2023q1 Homework1 (quiz1)
contributed by < `paul90317` >
[題目連結](https://hackmd.io/@sysprog/linux2023-quiz1)
### 測驗 `1`
快速排序程式碼填空
```c
static void list_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
/* 宣告左右兩 list */
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
/* 以第一個節點當 pivot */
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
/* 大小分割 */
struct item *itm = NULL, *is = NULL;
CCC (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
DDD (&itm->list, &list_less);
else
EEE (&itm->list, &list_greater);
}
list_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
}
```
`list_first_entry` 的輸入是節點 `head`，輸出是 `entry` 所以會用到 `container_of`，故 `AAA` 是 `struct item`，`BBB` 是 `list`。
`CCC` 是 `list_for_each_entry_safe`。
`DDD` 這個程式碼發生在 `itm` 比 `pivot` 小時發生。題目要求是該排序演算法要是 stable，所以應填入 `list_add_tail`。
`EEE` 同 `DDD`，也是 `list_add_tail`。
`FFF` 可以看出程式碼想要以 `list_less`, `pivot`, `list_greater` 建立新的 list 於 `head`，所以要填 `list_splice_tail`。
:::danger
在 `DDD` `FFF` 的程式碼中，忘記把 `itm` 從原本的 list 中移除，正確答案應該要是 `list_move_tail`。
如果要填 `list_add_tail`，就要在分割結束串接之前加上 `INIT_LIST_HEAD(head)`。
參考：[`as200188`](https://hackmd.io/@as200188/linux2023-quiz1)
:::
### 測驗 `2`
```c=
#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
INIT_LIST_HEAD(&stack[i]);
int top = -1; // top 代表最後一個 list，而非下一個
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
/* 每次執行 statement 相當於遞迴呼叫 */
while (top >= 0) {
INIT_LIST_HEAD(&partition);
/* 在 stack 頂部拿取一個 partition 進行排序 */
list_splice_init(&stack[top--], &partition);
/* 如果 partition 不為空 */
if (!list_empty(&partition) && !list_is_singular(&partition)) {
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
/* 選取第一個節點當作 pivot */
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
/* 分成大小兩邊 */
struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
list_del(&itm->list);
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
/* 這裡換成 list_stable 才能
* 達到 stable sort 的目的 */
}
/* 將 pivot 接在 list_less 後面 */
HHHH (&pivot->list, &list_less);
/* 將左右兩條 list (未經 partition) 推入 stack */
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
/* 應先放入 greater 再放 less，因為下方程式碼
* 會將 list 從頂部取出再推入 head 的尾巴 */
/* 若 partition 為空或只有單一元素 */
} else {
/* 直接推入 stack */
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
/* 當 list 只有單一節點，將 list 拿出並插入 head 尾端 */
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(KKKK);
list_add_tail(&tmp->list, head);
}
}
}
}
```
`GGGG` 是 `list_for_each_entry_safe`
`HHHH` 是 `list_add_tail`
`IIII` 是 `&stack[++top]`
`JJJJ` 是 `&stack[++top]`
`KKKK` 是 `&tmp->list`
:::success
**1. 解釋上方程式碼運作原理，指出設計和實作的缺失**
* 在 40、42 行應該改成 `list_add_tail` 以達到 stable sort 的目的。
* 在 115 行應該改成 `if (!list_empty(!list_empty(&partition)))` 以防止將空的 list 推入並造成無窮迴圈。
:::
### 測驗 `3`
```c
typedef struct _xorlist_node {
struct _xorlist_node *cmp;
} xor_node_t;
typedef struct _xor_list_struct {
xor_node_t head, tail;
uint32_t count;
} xor_list_t;
struct test_node {
int value;
xor_node_t xornode;
};
#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))
```
根據題目說明，要把前一節點和後一節點的指標做相連，`LLLL` 是 `a & b`
```c
#define xorlist_for_each(node, rp, rn, list) \
for (rp = &(list)->head, node = rp->cmp; node != &(list)->tail; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
```
上方巨集迴圈初始化部分會將 node 直接指派成 `list->head.cmp`，這意味著第一個節點 (first entry) 不是 `list->head`，而是 `list->head` 的下一節點。
`rp` 是上一節點的指標，所以在迴圈迭代下一節點是 `rn = address_of(rp, node->cmp)`。
當 `node` 是 `&list->tail` 的時候，會跳出迴圈，因為它的容器是 `xor_list_t` 而非自訂義容器 `struct test_node`。
```c
#define xorlist_for_each_prev(node, rp, rn, list) \
for (rp = &(list)->tail, node = rp->cmp; node != &(list)->head; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
```
上方巨集的走訪方向與 `xorlist_for_each` 相反。
```c
#define xorlist_for_each_from(node, pos1, pos2, rp, rn, list) \
for (rp = pos2, node = pos1; node != &(list)->tail; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
```
上方巨集定義了初始節點 `pos2`，需要再給它 `pos1` 以獲得下一節點。
```c
#define xorlist_for_each_from_prev(node, pos1, pos2, rp, rn, list) \
for (rp = pos1, node = pos2; node != &(list)->head; \
rn = address_of(rp, node->cmp), rp = node, node = rn)
```
上方巨集的走訪方向與 `xorlist_for_each_from` 相反。
```c=
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
/* n 的下一節點 */
xor_node_t *real_next;
if (!n)
return ENOMEM;
/* n 的前一節點，也就是 head */
xor_node_t *real_prev = &list->head;
/* node 是原本的第一個節點 */
xor_node_t *node = real_prev->cmp;
/* 對 n 的下一節點指派 */
if (node == &list->tail)
real_next = MMMM;
else
real_next = node;
/* 將 head->cmp 直接指派為 n 因為 head 沒有前一節點 */
real_prev->cmp = n;
/* 根據定義指派 n->cmp */
n->cmp = XOR_COMP(real_prev, real_next);
/* real_next 是 node
* node 的 cmp 是 n (node 的前一節點) 與 node 的下一節點的 xor
* 故 XOR_COMP(real_prev, PPPP) 是 node 的下一節點
* PPPP 是 node->cmp */
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
list->count++;
return 0;
}
```
`real_next` 是 `n` 的下一個節點，在一般的情況下它是原本的第一個節點 `node`，但在沒有節點時它是 tail，故 `MMMM` 是 `&list->tail`。
`PPPP` 是 `node->cmp`
Sign in with Wallet
Connect another wallet