---
tags: Linux, C
---
# 2023q1 Homework1 (quiz1)
contributed by <[huanginch](https://github.com/huanginch/)>
>[題目](https://hackmd.io/@sysprog/linux2023-quiz1)
## 測驗一
### struct item
```c
#include <stdint.h>
#include "list.h"
struct item {
uint16_t i;
struct list_head list;
};
```
此段程式碼為宣告item結構，item 包含一個數值 i 與一個嵌入至 item 的 list_head。
### cmpint
```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;
}
```
此段程式碼進行節點的大小比較，透過相減的方式，若 i1 的值大於 i2 會回傳正數(i1 - i2 > 0)，小於回傳負數(i1 - i2 < 0)，相等則回傳 0。
### list_sort
```c
if (list_empty(head) || list_is_singular(head))
return;
```
首先此段程式碼判斷 list 是否為 empty 或只有一個節點，是的話就直接 return (不需要 sort )。
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
使用 INIT_LIST_HEAD 這個巨集來產生 list_less 與 list_greater 兩個 list，分別用來儲存小於 pivot 的 list 與大於 pivot 的 list。
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
```
使用 list_first_entry 巨集從 head (也就是我們的排序目標) 取得第一個節點，並將 pivot 指向此節點。
參考 [list_first_entry](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_first_entry)的說明可以得知，此巨集第二個參數需要自訂 struct 的名稱，也就是 `struct item`，第三個變數為這個 struct 中 `list_head` 的名稱，也就是 `list`。
:::info
此處 AAA 要填入 ```sruct item```， BBB 要填入 ```list```
:::
```c
list_del(&pivot->list);
```
將 pivot 的 list 移走，因為在做quick sort 時，pivot 會重新連接 list_less 和 list_greater，所以舊的指向的 list 必須移除。
```c
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);
}
```
這段在做 quick sort 中的比大小，針對目標 list (head) 中的每個節點，如果值比 pivot 的值小就放入 list_less，大於或等於放入 list_greater。
同時依照傳入的參數來判斷，CCC使用的是 `list_for_each_entry_safe`
需傳入四個參數，其中前兩個分別用途為 *itm 作為 cursor、*is 用來做 temporary storage。
可參考 [API文件](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_for_each_entry_safe)
:::info
CCC 要填入 `list_for_each_entry_safe`
DDD 要填入 `list_add`
EEE 要填入 `list_add`
:::
#### stable sorting
:::warning
為了實現 stable sorting ，值與 pivot 相等的節點不能放入 list_less
:::
考慮以下情況:
因為我們使用 head list 中的第一個節點當作 pivot，同時他的值為3，我們暫時將它稱為 $3_1$，此時 head 中第二個節點的值也是3，我們暫時稱它為$3_2$，而 stable sorting 所要求的是排序後的 list 也能維持 $3_1$, $3_2$的順序，因為我們排序後會依照 list_less、pivot、list_greater的順序連上，所以假設我們將等於 pviot 的值放入 list_less，會導致 $3_2$, $3_1$。
```c
list_qsort(&list_less);
list_qsort(&list_greater);
```
這兩段程式碼有錯，這邊該執行的是遞迴呼叫 list_sort 以排序剛剛分好的兩個 list。
```c
list_sort(&list_less);
list_sort(&list_greater);
```
以上才是正確寫法。
```c
list_add(&pivot->list, head); // head->pivot
list_splice(&list_less, head); // list_less->head
FFF(&list_greater, head); // head->list_greater
```
最後將排序好的 list_less、pviot、list_greater 依照順序接上，就會得到排序好的 list。
* 因為 pivot 是一個節點，所以使用 list_add
* 因為要將 list_less 接在 head 之前，所以使用 list_splice
* 因為要將 list_greater 接在 head 之後，所以使用 list_splice_tail
:::info
FFF 要填入 `list_splice_tail`
:::
Sign in with Wallet
Connect another wallet