owned this note
owned this note
Published
Linked with GitHub
# 2023q1 Homework1 (quiz1)
###### tags: `2023-linux_kernel`
contributed by < `JoshuaLee0321` >
## 第一週測驗題
### 測驗一
[2023q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)
題目敘述如下：
* 給定一個結構體如下
```c
struct item {
uint16_t i;
struct list_head list;
};
```
* 是一個以 doubly linked 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;
}
```
而目標為利用 `linux/list.h` 中的 API 對快速排序法實作
* 基本上快速演算法為一種 [`divide and conquer 演算法`](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm)，而很明顯的這個演算法就會把給定的 linked list 分為兩半來處理，除此之外還要保證 stable
* 題目code 如下：
:::spoiler
```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);
}
```
:::
* 由於知道是 quick sort，我們就可以直接填入以上AAA 到 FFF 了
* struct item *pivot = list_first_entry(head, AAA, BBB);
* 以這行為例
* pivot 不外乎就是快速排序法中取出pivot，而這邊直接使用 list_first_entry來取出
* 所以 AAA 很明顯就是 ==item==
* BBB 就是 ==list==
* CCC 吃四個參數，主要是為了把最前面的itm 移除掉後給list_less 或 list_greater，所以
* CCC 為 ==list_for_each_entry_safe==
* DDD 為 ==list_move_tail==
* EEE 為 ==list_move_tail==
* 最後的 FFF，由於是已經把 list_greater 排序好了，而很明顯這個已經排序好的 linked list 為比較大的鏈結串列，那只需要把他接在最後面，這個排序就完成了。
* FFF 為 ==list_splice_tail==
### 延伸問題
#### 一、
#### 二、
#### 三、
#### 四、
### 測驗二
* 給定程式碼如下：
* 找出 GGGG HHHH IIII JJJJ KKKK
* 這個程式碼，根據題目敘述，為iterative 版本的 quick sort
:::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;
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);
}
}
}
}
```
:::
* 我們一一來分解以上code到底在做甚麼
```c
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);
```
* 一開始這幾行都在把 stack 設定好，並且把 head 放入 &stack[0]的位置
:::warning
2023/2/28 老師我想要請問為甚麼要寫
```c
int top = -1;
list_splice_init(head, &stack[++top]);
```
而不是
```c
int top = 0;
list_splice_init(head, &stack[top]);
```
這樣意義何在？多做一件事情不是會多消耗資源嗎?
:::
* 後面的while 大致上可以分成
1. 從stack 中取出需要的 partition
2. 對partition 進行排序並且放回stack中
3. 若從stack 中取出的partition沒有東西，則把排序好的list 放回head 中
* 知道這個基本結構之後，我們就可以來看看填空的區域了
```c
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);
}
```
* `GGGG` 很明顯就是 `list_for_each_entry_safe`
```c
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);
```
* `HHHH` 看起來就是要把 `pivot` 放入 `list_less` 中，而由於在 `quicksort` 中 `pivot` 會是 `list_less` 中最大的元素，故把他擺到 `list_less` 中的最後一位，也就是==list_move_tail==
* 其實也可以改成 ==`list_move(&pivot->list, &list_greater)`==
* `IIII` 跟 `JJJJ` 的意思為，當 `list_greater 或是 list_less` 中有東西的話，我就把他們擺入stack中，所以這邊應該要寫 ==`&stack[++top]`== 如此一來可以保證 top往上移動並且不會撞到原本的元素
```c
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);
}
}
```
* 最後一個部分為把 `stack` 中的元素放入 原本的 `head` 中，一一把排序好的元素放回head中。
* 很明顯的就是要把 `stack[top]` 的元素拿出來之後並且初始化
* 所以 `KKKK` 很明顯的就是 &stack[top--]
:::info
其實這四行程式碼可以省略成一行，變成以下:
`list_move_tail(&stack[top--], head)`
:::
### 測驗三
Google Drive
Gist
Clipboard
Sign in with Wallet
