---
title: 2023q1 Homework1 (quiz1)
tags: Linux核心設計
---
# [2023q1 Homework1 (quiz1)](https://hackmd.io/@sysprog/linux2023-quiz1)
## [測驗一](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-1)
給定 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 作為[〈linked list 和非連續記憶體操作〉](https://hackmd.io/@sysprog/c-linked-list)提及的 Linux 核心風格 circular doubly-linked list 實作，欲處理的節點採用以下結構體:
```c
#include <stdint.h>
#include "list.h"
struct item {
uint16_t i;
struct list_head list;
};
```
用以對節點內含值比較的函式:
```c
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;
}
```
以下程式碼實作快速排序法，數值由小到大排列，並確保可達到 [stable sorting](https://en.wikipedia.org/wiki/Sorting_algorithm) 的目標。
```c
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, 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);
}
```
請補完，使其行為符合預期。作答規範:
* AAA, BBB, CCC, DDD, EEE, FFF 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)，均不包含小括號 (即 ( 和 ))，且不可出現 , 和 ; 這樣的分隔符號 (separator)
* BBB 為 identifier
* CCC, DDD, EEE, FFF 均為以 list_ 開頭的巨集 (macro)
### 程式碼原理
1. 首先先來看 `list_first_entry` 此巨集的參數，為 `list_first_entry(head, type, member)` ，可知 `AAA` 會是 `type of the entry`，即為 `item` ， `BBB` 則是 member variable ， item member variable 有兩種，為 `uint16_t i` 與 `struct list_head list;` ，而 `pivot` 要取得 list 的第一個位置，所以 `BBB` 即為 `list`。
2. `CCC (itm, is, head, list)` 為含有 4 個參數的巨集，且排序法須對每個節點走訪，所以 `CCC` 即為 `list_for_each_entry_safe` 。
3. 再迴圈中使用 `cmpint` 來比大小，比 `pivot` 小的節點接到 `list_less` 後面，比 `pivot` 大的節點接到 `list_greater` 後面，所以 `DDD` 與 `EEE` 皆為 `list_move` 。
4. 最後將 `pivot`, `list_less`, `list_greater` 串起來，`list_greater` 要串接在 list 後面，所以 `FFF` 即為 `list_splice_tail` 。
### 答案
:::success
* `AAA = item`
* `BBB = list`
* `CCC = list_for_each_entry_safe`
* `DDD = list_move`
* `EEE = list_move`
* `FFF = list_splice_tail`
程式碼
```c
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, 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 (&itm->list, &list_less);
else
list_move (&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);
}
```
:::
## [測驗二](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-2)
延續上方測驗 `1`，參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)，將以下程式碼改寫為非遞迴 (non-recursive; iterative) 的實作:
```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;
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
while (top >= 0) {
INIT_LIST_HEAD(&partition);
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;
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);
}
HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
} else {
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(KKKK);
list_add_tail(&tmp->list, head);
}
}
}
}
```
### 程式碼原理
1. `GGGG (itm, is, head, list)` 為含有 4 個參數的巨集，且排序法須對每個節點走訪，所以 `GGGG` 即為 `list_for_each_entry_safe` 。
2. 再進入迴圈前，會先將 inpur list ，也就是 `stack[0]` 接在 `partition` 後，當 `partition` 不為空也不為單時，會初始化 `list_less` 與 `list_greater` ，並將比 `pivot` 小的節點接到 `list_less` 後面，比 `pivot` 大的節點接到 `list_greater` 後面，而 `HHHH (&pivot->list, &list_less);` ，因為 `pivot` 比 `list_less` 都還大，故應將 `pivot` 接在`list_less` 後，所以 `HHHH` 即為 `list_add_tail` 。
3. 此時分類完的`list_greater` 與 `list_less` 應放入 `stack` 中，，此時 `top = -1;` ，所以應先將 `top++;` ，再將 `list_greater` 與 `list_less` 個別放入 `stack` 裡，所以綜合以上兩步驟， `IIII` 與 `JJJJ` 即為 `stack[++top]` 。
4. 若 `partition` 為空或為單，則進入 `else` 裡面，若 `partition` 有一個值，那必定是最小值，將這個值放入最上層的 `stack` 裡，並將該值接到 `head` 後面，而 `top` 會指向下一層，所以須做 `top--;` ，綜合以上兩步驟，可知 `KKKK` 即為 `stack[top--]` 。
### 答案
:::success
* `GGGG = list_for_each_entry_safe`
* `HHHH = list_add_tail`
* `IIII = stack[++top]`
* `JJJJ = stack[++top]`
* `KKKK = stack[top--]`
程式碼
```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;
list_splice_init(head, &stack[++top]);
struct list_head partition;
INIT_LIST_HEAD(&partition);
while (top >= 0) {
INIT_LIST_HEAD(&partition);
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;
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 {
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);
}
}
}
}
```
:::
## [測驗三](https://hackmd.io/@sysprog/linux2023-quiz1#%E6%B8%AC%E9%A9%97-3)
XOR 運算特性:
$A⊕A=0$
$A⊕0=A$
$A⊕1=¬A$
$(A⊕B)⊕B=A$
以下程式碼是個 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的實作，在這樣的資料結構可表示為:
```
1 2 3 4
data HAT CAT EAT BAT
link 2 2 6 3
```
要往下一格移動時，我們需要前一格在哪和這一格的位置。例如我們現在在 HAT (1), 已知前一格是 (0)，那麼下一格就是 link(1) XOR 0 = 2 XOR 0 = 2，也就是 CAT。繼續，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，依此類推。只要當找出來的下一格是 (0) 就結束。
[XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list) 的優勢在於空間的佔用更精簡，與尋常作法相比，佔用的儲存空間比值會趨近 67%
。
以下是學習 Linux 核心 list.h 風格的 XOR linked list 實作，其中 ## 為 C 語言前置處理器，參見 [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)
參考執行輸出：
```
xorlist_for_each test
node [0] 999
node [1] 998
node [2] 997
...
node [996] 2
node [997] 1
node [998] 0
```
程式碼列表:
```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 *) (LLLL))
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 = MMMM;
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, PPPP));
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;
}
```
請補完程式碼，使其運作符合預期。作答規範:
* LLLL 為表示式，在運算子前後要一個空白字元區隔，應包含 uintptr_t，符合 lab0-c 預期的排版風格
* MMMM 和 PPPP 為表示式
### 程式碼原理
```
1 2 3 4
data HAT CAT EAT BAT
link 2 2 6 3
```
1. 以上例為例，現在位於 CAT (2)，前一格在 (1)，於是下一格就是 link(2) XOR 1 = 2 XOR 1 = 3，亦即 EAT，也就是說：**前一格 XOR link = 下一格**，而 **前一格 XOR 下一格 = link** ，所以只要 link 存的是 前一格 XOR 下一格 的值，我們就能用前一格與 link 的值去找到下一格，所以也不難看出 `struct _xorlist_node *cmp;` 存的是 link 的值，在函式 `xorlist_add` 中的 `n->cmp = XOR_COMP(real_prev, real_next);` 就是要將 link 值放入 `cmp` 中，所以 `#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))` 中的 `LLLL` 為將兩個值做 XOR ，即為 `(uintptr_t)(a) ^ (uintptr_t)(b)` 。
2. 在函式 `xorlist_add` 中，目的是將節點 `n` 加入到 list 中，當 `n` 為最後的節點時，它的下一個節點即為自己，因為自己 XOR 自己 = 0，也就是下一格，所以 `MMMM` 為 `&list->tail` 。
3. `real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));` ，節點 `n` 的下一個節點的 link 值即為 **前一格 XOR 下一格**，也就是 `n` XOR `real_next->next` ，而下一格可以從 **前一格 XOR 自己本身的 link 值**取得，所以 `PPPP` 為自己本身的 link 值，也就是 `real_next->cmp` 。
### 答案
:::success
* `LLLL = (uintptr_t)(a) ^ (uintptr_t)(b)`
* `MMMM = &list->tail`
* `PPPP = real_next->cmp`
:::
Sign in with Wallet
Connect another wallet