---
tags: linux2023
---
# 2023q1 Homework1 (quiz1)
contributed by < [KHLee529](https://github.com/KHLee529) >
> [測驗問題](/@sysprog/linux2023-quiz1)
## 測驗 `1`
### 作答結果
- `AAA`: `struct item`
- `BBB`: `list`
- `CCC`: `list_for_each_entry_safe`
- `DDD`: `list_move_tail`
- `EEE`: `list_move_tail`
- `FFF`: `list_splice_tail`
:::spoiler 程式碼
```c
#include <stdint.h>
#include "list.h"
struct item {
uint16_t i;
struct list_head list;
};
static inline int cmpint(const void *p1, const void *p2)
{
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
static void list_sort(struct list_head *head)
{
if (list_empty(head) || list_is_singular(head))
return;
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
struct item *pivot = list_first_entry(head, struct item, list);
list_del(&pivot->list);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move_tail (&itm->list, &list_less);
else
list_move_tail (&itm->list, &list_greater);
}
list_sort(&list_less);
list_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
:::
### 程式運作原理
首先以一個長度為 5 的串列進行演算法的演示如下所示。
```graphviz
digraph {
label="Initial"
rankdir=LR;
node[shape=record];
h[label="head|{<p>prev|<x>next} "];
n1[label="node 1|{<p>prev|<x>next} "];
n2[label="node 2|{<p>prev|<x>next} "];
n3[label="node 3|{<p>prev|<x>next} "];
n4[label="node 4|{<p>prev|<x>next} "];
n5[label="node 5|{<p>prev|<x>next} "];
h:x->n3:w
n3:x->n4:w
n4:x->n1:w
n1:x->n2:w
n2:x->n5:w
n5:p->n2:e
n2:p->n1:e
n1:p->n4:e
n4:p->n3:e
n3:p->h:e
}
```
首先選擇第一個節點作為 pivot，用於將剩餘的節點做大小分類。
```graphviz
digraph {
label="Take first node as pivot"
rankdir=LR;
node[shape=record];
h[label="head|{<p>prev|<x>next}"];
n1[label="node 1|{<p>prev|<x>next}"];
n2[label="node 2|{<p>prev|<x>next}"];
n3[label="node 3|{<p>prev|<x>next}"];
n4[label="node 4|{<p>prev|<x>next}"];
n5[label="node 5|{<p>prev|<x>next}"];
p[label="pivot", shape=plaintext]
p->n3:w
h:x->n4:w
n4:x->n1:w
n1:x->n2:w
n2:x->n5:w
n5:p->n2:e
n2:p->n1:e
n1:p->n4:e
n4:p->h:e
}
```
接著逐一走過每一個節點，按照與 pivot 節點的值大小比較分成 `list_greater` 與 `list_less` 兩條。之後遞迴的對於這兩個串列再進行排序。
**注意**: 由於需要確保 stable sorting 的性質，必須維持原先的順序，故 `DDD` 與 `EEE` 需使用 `list_move_tail` 而非 `list_move`。
```graphviz
digraph {
label="Separate list into two list \n <list_greater> and <list_less> and sort them"
rankdir=LR;
node[shape=record];
h[label="head|{<p>prev|<x>next}"];
n1[label="node 1|{<p>prev|<x>next}"];
n2[label="node 2|{<p>prev|<x>next}"];
n3[label="node 3|{<p>prev|<x>next}"];
n4[label="node 4|{<p>prev|<x>next}"];
n5[label="node 5|{<p>prev|<x>next}"];
p[label="pivot", shape=plaintext]
ll[label="list_less", shape=plaintext]
lg[label="list_greater", shape=plaintext]
h
p->n3:w
lg->n4:w
n4:x->n5:w
ll->n1:w
n1:x->n2:w
n5:p->n4:e
n2:p->n1:e
}
```
最後依序將排序好的 `list_less`、`pivot`、排序好的 `list_greater` 接回原本的串列便完成整個串列的排序。
```graphviz
digraph {
label="Merge them all in the order\n<list_less>-<pivot>-<list_greater>"
rankdir=LR;
node[shape=record];
h[label="head|{<p>prev|<x>next}"];
n1[label="node 1|{<p>prev|<x>next}"];
n2[label="node 2|{<p>prev|<x>next}"];
n3[label="node 3|{<p>prev|<x>next}"];
n4[label="node 4|{<p>prev|<x>next}"];
n5[label="node 5|{<p>prev|<x>next}"];
p[label="pivot", shape=plaintext]
ll[label="list_less", shape=plaintext]
lg[label="list_greater", shape=plaintext]
p->n3:n
ll->n1:n
lg->n4:n
h:x->n1:w
n1:x->n2:w
n2:x->n3:w
n3:x->n4:w
n4:x->n5:w
n5:p->n4:e
n4:p->n3:e
n3:p->n2:e
n2:p->n1:e
n1:p->h:e
}
```
## 測驗 `2`
### 作答結果
- `GGGG`: `list_for_each_entry_safe`
- `HHHH`: `list_add_tail`
- `IIII`: `&stack[++top]`
- `JJJJ`: `&stack[++top]`
- `KKKK`: `&stack[top--]`
:::spoiler 程式碼
```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;
/* add the origin list into stack */
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
/* process while stack are not empty */
while (top >= 0) {
INIT_LIST_HEAD(&partition);
/* take the first list in stack to process */
list_splice_init(&stack[top--], &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);
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;
/* separate list into greater and less comparing to pivot */
list_for_each_entry_safe (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_add_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
} else {
/* if partition is empty or singular */
top++;
list_splice_tail(&partition, &stack[top]);
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp =
list_first_entry(&stack[top], struct item, list);
list_del(&tmp->list);
INIT_LIST_HEAD(&stack[top--]);
list_add_tail(&tmp->list, head);
}
}
}
}
```
:::
### 程式運作原理
以一個六個節點的串列進行演示。
首先將整個串列加入堆疊 (stack) 的頂端，如下圖所示，開始進行迭代式的快速排序。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
stack[shape=plaintext]
s[label="<1>top|<2>|<3>|<4>|<5>|<6>|..."]
n1[label="1|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
stack->s:n
s:1->n3:w
n3:x->n4:w
n4:x->n6:w
n6:x->n5:w
n5:x->n2:w
n2:x->n1:w
n1:p->n2:e
n2:p->n5:e
n5:p->n6:e
n6:p->n4:e
n4:p->n3:e
n3:p->s:1
}
```
取出位在堆疊頂部的串列，並取第一個節點作為 pivot 後，將整個串列根據其值與 pivot 的先後關係分成 `list_greater` 與 `list_less`。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>|<3>|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
p[label="pivot" shape=plaintext]
lg[label="list_greater" shape=plaintext]
ll[label="list_less" shape=plaintext]
stack->s:n
p->n3:w
lg->n4:w
n4:x->n6:w
n6:x->n5:w
ll->n2:w
n2:x->n1:w
n5:p->n6:e
n6:p->n4:e
n1:p->n2:e
}
```
接著將 pivot 接上 `list_less` 的最後端後將 `list_greater` 與 `list_less` 分別推入堆疊中。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>top|<3>|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
s:1->n4:w
n4:x->n6:w
n6:x->n5:w
s:2->n2:w
n2:x->n1:w
n1:x->n3:w
n5:p->n6:e
n6:p->n4:e
n1:p->n2:e
n3:p->n1:e
}
```
接著進入下一次迭代，再將原先在堆疊頂端的串列取出，進行與前述相同的操作後放回堆疊。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>|<3>top|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
s:1->n4:w
n4:x->n6:w
n6:x->n5:w
s:3->n1:w
n1:x->n2:w
s:2->n3:w
n5:p->n6:e
n6:p->n4:e
n2:p->n1:e
}
```
再進行一次相同的流程。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>|<3>|<4>top|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
s:1->n4:w
n4:x->n6:w
n6:x->n5:w
s:3->n2:w
s:4->n1:w
s:2->n3:w
n5:p->n6:e
n6:p->n4:e
}
```
此時由於堆疊頂端的串列僅有一個元素，此時依序將只有一個元素的串列接上 `head`。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>top|<2>|<3>|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
s:1->n4:w
n4:x->n6:w
n6:x->n5:w
n5:p->n6:e
n6:p->n4:e
h:x->n1:w
n1:x->n2:w
n2:x->n3:w
n3:p->n2:e
n2:p->n1:e
n1:p->h:e
}
```
對剩下來的串列再做一次上述的拆分流程。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>|<3>top|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
s:1->n6:w
s:2->n5:w
s:3->n4:w
h:x->n1:w
n1:x->n2:w
n2:x->n3:w
n3:p->n2:e
n2:p->n1:e
n1:p->h:e
}
```
最後當堆疊清空時迭代結束，完成排序。
```graphviz
digraph {
node[shape=record];
rankdir=LR;
h[label="head|{<p>prev|<x>next}"]
s[label="<1>|<2>|<3>|<4>|<5>|<6>|..."]
stack[shape=plaintext]
n4[label="4|{<p>prev|<x>next}"]
n5[label="5|{<p>prev|<x>next}"]
n6[label="6|{<p>prev|<x>next}"]
n2[label="2|{<p>prev|<x>next}"]
n1[label="1|{<p>prev|<x>next}"]
n3[label="3|{<p>prev|<x>next}"]
//p[label="pivot" shape=plaintext]
//lg[label="list_greater" shape=plaintext]
//ll[label="list_less" shape=plaintext]
stack->s:n
h:x->n1:w
n1:x->n2:w
n2:x->n3:w
n3:x->n4:w
n4:x->n5:w
n5:x->n6:w
n6:p->n5:e
n5:p->n4:e
n4:p->n3:e
n3:p->n2:e
n2:p->n1:e
n1:p->h:e
}
```
### 程式實作缺失
1. 在拆分為 `pivot`、`list_greater`、`list_less` 的三個部份後，由於已經確定 `list_less` 的所有節點值都小於 `pivot`，應將 `pivot` 節點單獨推入堆疊中，否則會增加所需要的比較次數以及操作次數，修改如下
```diff
diff --git a/origin.c b/modified.c
index 62b862c..b056693 100644
--- a/origin.c
+++ b/modified.c
@@ -36,9 +36,9 @@ static void list_sort_nr(struct list_head *head) {
list_move(&itm->list, &list_greater);
}
- list_add_tail(&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
+ list_add(&pivot->list, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
} else {
```
## 測驗 `3`
### 作答結果
- `LLLL`: `(uintptr_t) (a) ^ (uintptr_t) (b)`
- `MMMM`: `node`
- `PPPP`: `real_next->cmp`
:::spoiler 程式碼
```c
#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
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;
#define XOR_COMP(a, b) ((xor_node_t *) ((uintptr_t) a ^ (uintptr_t) b))
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
assert(n1 && n2);
return XOR_COMP(n1, n2);
}
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#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)
#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)
#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)
#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)
/* Note that when the delete function success is must return 0. */
#define xorlist_delete_prototype(name, node) \
int _xorlist_delete_##name(xor_node_t *node)
#define xorlist_delete_call(name) _xorlist_delete_##name
static inline xor_node_t *xornode_init(xor_node_t *n)
{
assert(n);
n->cmp = NULL;
return n;
}
#define XORNODE_INIT(n) \
do { \
(n).cmp = NULL; \
} while (0)
#define XORLIST_INIT(h) \
do { \
(h).head.cmp = &(h).tail; \
(h).tail.cmp = &(h).head; \
(h).count = 0; \
} while (0)
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
xor_node_t *real_next;
if (!n)
return ENOMEM;
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
if (node == &list->tail)
real_next = node;
else
real_next = node;
real_prev->cmp = n;
n->cmp = XOR_COMP(real_prev, real_next);
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp);
list->count++;
return 0;
}
int xorlist_del(xor_list_t *list,
xor_node_t *n,
xor_node_t *target,
int (*delete_func)(xor_node_t *))
{
assert(list && n && target && delete_func);
assert(&list->head != target && &list->tail != target);
xor_node_t *nn = address_of(target, n->cmp);
xor_node_t *an = address_of(n, target->cmp);
xor_node_t *ana = address_of(target, an->cmp);
n->cmp = XOR_COMP(nn, an);
an->cmp = XOR_COMP(n, ana);
delete_func(target);
list->count--;
return 0;
}
int xorlist_destroy(xor_list_t *list, int (*delete_func)(xor_node_t *))
{
assert(delete_func);
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
xor_node_t *real_next = address_of(real_prev, node->cmp);
xor_node_t *tmp = real_prev;
real_prev = node;
node = real_next;
while (node != &list->tail) {
real_next = address_of(real_prev, node->cmp);
tmp = real_prev;
real_prev = node;
node = real_next;
if (delete_func(tmp) != 0)
perror("delete function failed");
}
return 0;
}
struct test_node {
int value;
xor_node_t xornode;
};
xorlist_delete_prototype(test_delete, _node)
{
struct test_node *node = container_of(_node, struct test_node, xornode);
free(node);
return 0;
}
int main(void)
{
xor_list_t list;
xor_node_t *p1, *p2;
XORLIST_INIT(list);
for (int i = 0; i < 1000; i++) {
struct test_node *new = malloc(sizeof(struct test_node));
xornode_init(&new->xornode);
new->value = i;
xorlist_add(&list, &new->xornode);
if (i == 5)
p1 = &new->xornode;
if (i == 6)
p2 = &new->xornode;
}
xor_node_t *real_prev, *real_next, *node;
int i = 0;
printf("xorlist_for_each test\n");
xorlist_for_each(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_from test\n");
xorlist_for_each_from(node, p1, p2, real_prev, real_next, &list)
{
printf("node %d\n",
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_each_from_prev test\n");
xorlist_for_each_from_prev(node, p1, p2, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
i = 0;
printf("xorlist_for_each_prev test\n");
xorlist_for_each_prev(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
printf("xorlist_del test\n");
xorlist_del(&list, p2, p1, xorlist_delete_call(test_delete));
i = 0;
xorlist_for_each(node, real_prev, real_next, &list)
{
printf("node [%d] %d\n", i++,
container_of(node, struct test_node, xornode)->value);
}
xorlist_destroy(&list, xorlist_delete_call(test_delete));
return 0;
}
```
:::
### 程式運作原理
以下示意圖表示實作的 Xorlist 在包含 0, 1, 2 個節點時分別的狀況。
當零個節點時，頭尾兩個成員分別在 `cmp` 持有對方的位址。
```graphviz
digraph {
node[shape=record]
rankdir=LR;
subgraph cluster_list{
label="list"
lh[label="head|&tail"]
lt[label="tail|&head"]
cnt[label="count|0"]
}
}
```
當一個節點時，頭尾兩個成員分別紀錄唯一的一個節點的位址。由此透過比對頭尾成員保存的位址是否相同，便可知道是否為長度為 1 的串列。
而此時唯一的成員 `node1` 的 `cmp` 成員紀錄 `head` 與 `tail` 兩個串列成員的位址進行 xor 運算後的結果。
```graphviz
digraph {
node[shape=record]
rankdir=LR;
subgraph cluster_list{
label="list"
lh[label="head|&node1"]
lt[label="tail|&node1"]
cnt[label="count|1"]
}
n1[label="node1|&head ^ &tail"]
lh:e->n1:w
n1:s->lt:e
}
```
當串列包含兩個節點時的狀況如下，除了 `head`、`tail` 成員以外的節點均紀錄其前後節點的地址 xor 運算結果。
```graphviz
digraph {
node[shape=record]
rankdir=LR;
subgraph cluster_list{
label="list"
lh[label="head|&node1"]
lt[label="tail|&node2"]
cnt[label="count|2"]
}
n1[label="node1|&head ^ &node2"]
n2[label="node2|&node1 ^ &tail"]
lh:e->n1:w
n1:e->n2:w
n2:s->lt:e
}
```
### 程式實作缺失
在加入節點的程式碼當中並不需要根據
Sign in with Wallet
Connect another wallet