---
tags: Linux Kernal
---
# 2023q1 Homework1 (quiz1)
contributed by < `POCHUN-CHEN` >
[2023q1 第 1 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz1)
## 測驗1
`struct item` 為參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)內的結構體，負責存值與順序的 `list` 分開寫，往後可以運用 [`contain_of`](https://hackmd.io/@sysprog/linux-macro-containerof) 。
```c
#include <stdint.h>
#include "list.h"
struct item {
uint16_t i;
struct list_head list;
};
```
```graphviz
digraph list{
rankdir=LR;
subgraph cluster_1 {
node [shape=record];
value1 [label="{i}"];
subgraph cluster_11 {
node [shape=record];
addr1 [label="{<prev> prev|<next> next}"];
label="struct list_head list";
}
label=item;
}
node [shape=none]
none1 [label = ""];
none2 [label = ""];
edge[weight=2];
none1:right:e -> addr1;
addr1:right:e -> none2;
edge[weight=1];
}
```
---
[為什麼要用 `static inline` ?](https://gcc.gnu.org/onlinedocs/gcc-4.9.4/gcc/Inline.html)
->主要目的為提升程式速度。
>the program behaves the same as if you had not used the inline keyword, except for its speed.
---
用以對節點內含值比較的函式:
```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;
}
```
`cmpint` 函數返回的整數值代表了比較 `p1` 和 `p2` 這兩個指向 `uint16_t` 數據的指標的結果。這種方式是用於標準庫函數 qsort 中，qsort 函數會根據 cmpint 函數的返回值來對數組進行排序。
| 比較結果 | 回傳 | Column 3 |
| -------- | -------- | -------- |
| `*i1` 大於 `*i2` | 正整數 | `p1` 排在 `p2` 後面 |
| `*i1` 等於 `*i2` | 0 | 排序不變 |
| `*i1` 小於 `*i2` | 負整數 | `p1` 排在 `p2` 前面 |
這樣可以實現**對任意類型**(因為有 `(const uint16_t *)` 指標轉型)的數據進行排序的功能。
Q: 為什麼要把兩個指標函式傳進 `cmpint` 函式，再用 `i1` 、 `i2` 來被賦值呢？
>`p1` 從指向 void 顯示轉型成 `(const uint16_t *)` (這邊是指轉換成指向 `const uint16_t` 的指標，會有這種括號寫法，是因為 `p1` 本來就是指標了)。
>再賦值給指向 `const uint16_t` 的 `i1` 。
>宣告 `i1` 、 `i2` 才不會影響到本來的。
:::info
上述問題
```c
static inline int cmpint(const void *p1, const void *p2)
{
return *((const uint16_t *) p1) - *((const uint16_t *) p2);
}
```
顯示指標轉型不會影響到原本 `p1` 、 `p2` 的值，因此這樣寫應該更精簡？
:::
顯式的指標型別轉換會更改指標指向型別的編碼方式嗎？
>顯式的指標型別轉換通常**不會**更改指標指向型別的編碼方式。指標的編碼方式（如指標的位元組長度、對齊方式等）是由編譯器和操作系統決定的，與指標指向的型別無關。因此，進行顯式的指標型別轉換時，==被指向的二進制內容不會改變==，只是指標的型別被視為不同的型別。把顯示指標轉型的指標解構後，會將指向的型別的二進位數值，利用轉換後的型別方式顯示值（可能會與原本不同，但是==二進位的部分是一樣==的，但有可能長度不同）
---
首先，來看看 `list_sort` 的程式碼
```c
if (list_empty(head) || list_is_singular(head))
return;
```
先檢查串列是否為空，或者是只有一個值（就不用排了）。
---
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
接下來建立 `list_less` 、 `list_greater` ，等等來存放，比原串列中某個數值大 / 小的數值們。
接下來 `INIT_LIST_HEAD`，負責把新建立的 `list_head` 初始化，一定要把 `prev` / `next` 的前 / 後指標定義。
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
```graphviz
digraph structs {
node[shape=record]
struct0 [label="<prev> prev|<next> next"];
struct0:prev -> struct0[arrowhead=vee, tailclip=true, arrowsize=1];
struct0:next -> struct0[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
補充說明，以 `list_less` 為例， `&list_less` 與 `&(list_less.prev)` 是同樣地址，因為結構體 `list_head` 內是按照 `*prev` 、 `*next` 排序，所以第一個結構的起始地址就代表結構體的地址。
:::info
是否可善用 Micro 來簡化程式碼？作法如下。
```c
LIST_HEAD(list_less);
LIST_HEAD(list_greater);
```
由於 `LIST_HEAD()` 本身就包含宣告、初始化，故可以簡化程式碼。
```c
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
:::
`LIST_HEAD(list_less)` = `struct list head list_less` + `INIT_LIST_HEAD(&list_less)`。
---
```c
struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);
```
接下來就要把剛剛 `list_sort` 函式的輸入參數引進來比較排序。這時候 `item` 結構可以用來包含順序串列與其節點內該有的值。之後我們就要來看 `list_first_entry()` 代表什麼意思，參考[`list.h`](https://github.com/sysprog21/lab0-c/blob/master/list.h)中，可得到以下定義。
```c
/**
* list_first_entry() - Get first entry of the list
* @head: pointer to the head of the list
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of first entry in list
*/
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
這時可以查詢到 [`list_entry`](https://hackmd.io/@sysprog/c-linked-list#list_entry) 是 `container_of` 等價的包裝，符合以 list_ 開頭的命名慣例，此處的 entry 就是 list 內部的節點。
**特別注意：在 `list_` 系列的 `member` ==都限定在 `list_head member`== 。**
:::info
如果 `list_` 系列的 `member` ，故意輸入 `struct` 中，不是 `list_head member` 的成員，會不會發生錯誤？
:::
接著了解 [`container_of(ptr, type, member)`](https://hackmd.io/@sysprog/linux-macro-containerof#container_of-實作手法) 的實作手法。
程式碼是從 struct 中的 member 推算出原本 struct 的位址。
* @ptr: 指向 `member` 的指標
* @type: 結構物件的資料型態
* @member: 結構物件中，成員變數名稱
* Return: 會回傳一個指向包含指定ptr的type結構的指標。
```graphviz
digraph list{
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
list0 [label="{<prev> prev|<next> next}"];
label="struct list_head head";
}
subgraph cluster_1 {
node [shape=record];
value1 [label="{i}"];
subgraph cluster_11 {
node [shape=record];
list1 [label="{<prev> prev|<next> next}"];
label="struct list_head list";
}
label=item;
}
list0:prev:w -> list1:next:e[arrowhead=vee, tailclip=true, arrowsize=1];
list0:next -> list1:prev[arrowhead=vee, tailclip=true, arrowsize=1];
list1:prev:w -> list0:next:e[arrowhead=vee, tailclip=true, arrowsize=1];
list1:next:e -> list0:prev:w[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
這裡需要討論一下細節，由目前的程式碼中，我們只知道，我們把 `list_head` 結構的 `head` 傳進來 `list_sort` 函式。但熟知 linux 風格的 linked list ，我們知道在這個未經過排序的串列中，也是由 `item` 結構，包裹著決定串列順序的 `list_head` linked list 結構。並且第一個 `list_head` 沒有被包含在 `item` 結構。
由此我們可以知道， `list_first_entry(head, AAA, BBB)` 可以看成 `container_of((head)->next, type, member)` ，藉此得到原本串列的第一個 `item` 記憶體位置。再將其賦值給 `pivot` 。
#### AAA,BBB = ?
由 `container_of(ptr, type, member)` 可知，
* AAA應為type，在這個程式內應為`item`。
* BBB應為member，在這個程式內應為`list` (因為我們知道linux 風格的 linked list ，是由 `item` 結構包裹，所以成員函數可以用 `item` 內部的 `struct list_head list` )。
再將 `pivot` 利用 `list_del(&pivot->list)` 從 `head` 這個串列中移除。
>這邊 `list_del(&pivot->list)` 應該也可以寫成 `list_del(&head->next)` 但是這樣很不直觀，我們都寫了 `pivot` ，就直接專注在該節點就好。
---
#### CCC = ?
觀察到後面出現 `cmpint` 比較大小的函示，可以推斷 CCC 應該為推進整個串列比較的迴圈函式。為了在宣告完 `pivot` 後，確保可以比較到串列中的每一個值，再參考輸入參數後，使用函式 `list_for_each_entry_safe`。
* CCC為`list_for_each_entry_safe`。
```c
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))d
```
透過額外的 `safe` 紀錄每個迭代 (iteration) 所操作的節點的下一個節點，因此目前的節點可允許被移走，其他操作則同為不可預期行為。
---
#### DDD,EEE = ?
當把 `head` 串列中的值比較大小後，移動到 `list_less` / `list_greater` 的尾部，使用函式 `list_move_tail` 。
* DDD 為 `list_move_tail` 。
* EEE 為 `list_move_tail` 。
---
```c
list_sort(&list_less);
list_sort(&list_greater);
```
這邊可以看出遞迴的結構，把原本串列按照數值大小分類。依序持續切到排序完成。
:::warning
比較[Merge Sort實作](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-的實作)。
:::
---
#### FFF = ?
當分類完比 `pivot` 大或小所組成的兩串列後，且經由迭代即可完成排序。將 `pivot` 與排序後的串列，依序串成與原先串列長度一致的新串列。
將 `pivot` 加入 list 中的 head ， `list_less` 用 `list_splice` 加在 `head` 後; `list_gearter` 用 `list_splice_tail` 加在 `head` 前。
* FFF為 `list_splice_tail` 。
---
補充資料：
#### [Timsort](https://en.wikipedia.org/wiki/Timsort)
:::spoiler ChatGPT對於Timsort的解釋
Timsort是一種在排序演算法中廣泛使用的混合排序演算法。它由Tim Peters於2002年開發，並在Python中成為預設排序演算法。Timsort結合了插入排序和歸併排序的優點，因此具有高效的排序速度和佔用較小的內存空間。
Timsort的基本思路是將數組分為若干個小塊，對每個小塊進行插入排序，然後將這些小塊進行歸併排序。在實際應用中，Timsort還有一些優化措施，例如檢測已經有序的塊，跳過已經有序的塊，使用二分查找尋找插入位置等等。
Timsort的時間複雜度為O(n log n)，在最壞情況下的時間複雜度為O(n log n)，空間複雜度為O(n)。Timsort是一種穩定的排序演算法，可以處理大規模的數據集，被廣泛應用於Java、Python等編程語言的標準庫中。
:::
#### [Introsort](https://en.wikipedia.org/wiki/Introsort)
:::spoiler ChatGPT對於Introsort的解釋
:::
---
### 延伸問題
- [x] 1. 解釋程式碼運作原理
1. Check linked list in ```head``` has more than two entry and not empty. If not return it.
2. Use ```INIT_LIST_HEAD``` to initialize two list structure we made.
3. Use ```list_first_entry``` to get first entry to set it as pivot.
4. Delete the pivot from linked list(use ```list_del```)
5. Compare through all list. Use ```strncmp``` to compare ```item->value``` to ```pivot->value```, and seperate them to each ```list_less``` and ```list_greater```.
6. Call ```q_sort``` to regress ```list_less``` & ```list_greater```.
7. Add pivot to list
8. Splice ```list_less``` before pivot in list.
9. Splice ```list_greater``` after pivot in list.
- [ ] 2. 針對 Quick sort 提出程式碼的改進方案並實作
- [ ] 3. 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] 4. BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
## 測驗2
參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)
### 答案解析
#### GGGG,HHHH = ?
由程式碼可知GGGG，此程式碼與遞迴版本對應，在比對`pivot`前，必需先確保可以比較到串列中的每一個值，使用函式`list_for_each_entry_safe`。
當把串列中的值補在`list_less`和`list_greater`的尾部，使用函式`list_move_tail`。
* GGGG為`list_for_each_entry_safe`。
* HHHH為`list_move_tail`。
#### IIII,JJJJ,KKKK = ?
* IIII為`&stack[top--]`。
* JJJJ為`&stack[top--]`。
* KKKK為`XXX`。
---
### 延伸問題
- [ ] 1. 解釋程式碼運作原理，指出設計和實作的缺失
- [ ] 2. 比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
- [ ] 3. 提出效能改進方案，特別是避免依賴 `MAX_DEPTH`
- [ ] 4. 引入 Introsort ，也就是 quick sort 和 heap sort (或其他可避免前者 $O(n^2)$ 最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 $2∗log(n)$ 次後還排序完成，那就很可能會得到 $O(n^2)$ 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 $O(nlogn)$
## 測驗3
### 答案解析
#### LLLL = ?
#### MMMM,PPPP = ?
---
### 延伸問題
- [ ] 1. 解釋程式碼運作原理，指出其實作缺陷並改進
- [ ] 2. 在 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
- [ ] 3. 修改 `xorlist_destroy`，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放
Sign in with Wallet
Connect another wallet