# 2023q1 Homework1 (quiz1)
contributed by < [`yanjiew1`](https://github.com/yanjiew1) >
GitHub 連結: <https://github.com/yanjiew1/linux23q1-quiz1>
## 開發與實驗環境
```bash
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 10
CPU max MHz: 3400.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
```
## 測驗1
我們先來看 `list_sort` 函式的程式碼。程式一開頭出現，這裡是判斷傳入的串列是不是空的，或是只有一個元素。若是這樣就不用再排序，直接 return 即可，這裡是 `list_sort` 遞迴的 base case 。
```c
if (list_empty(head) || list_is_singular(head))
return;
```
---
接下來看到宣告了 `list_less` 和 `list_greater` 還有 `pivot` 。可知這應該是一個 quick sort 演算法。
```c
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 *pivot = list_first_entry(head, AAA, BBB);` 由 `list_first_entry` 巨集的定義和說明可知，第二個參數要填入 container 的 type ，在這裡是 `struct item` ，而第三個參數要填入在 `struct item` 裡 `struct list_head` member 的名稱，故為 `list` 。
:::info
:::spoiler `list_first_entry` 資訊
以下為 `list.h` 中的 `list_first_entry` 巨集內容
```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)
```
:::
一開始 `pivot` 指向第一個元素
```graphviz
digraph graphname{
compound=true
rankdir = LR
node[shape=box]
head[shape=plaintext]
pivot[shape=plaintext]
A[label=4]
B[label=1]
C[label=3]
D[label=5]
E[label=2]
F[label=7]
pivot->A
head->A [lhead=cluster_H];
subgraph cluster_H {
A->B->C->D->E->F[arrowhead=none]
}
}
```
`list_del(&pivot->list);` 則是把 `pivot` 從原本在 `head` 的串列中取下來。故執行 `list_del` 後，`pivot` 不再屬於 `head`指向的 list
```graphviz
digraph graphname{
compound=true
rankdir = LR
node[shape=box]
head[shape=plaintext]
pivot[shape=plaintext]
A[label=4]
B[label=1]
C[label=3]
D[label=5]
E[label=2]
F[label=7]
pivot->A
head->B [lhead=cluster_H];
subgraph cluster_H {
B->C->D->E->F[arrowhead=none]
}
}
```
---
接下來即將進入迴圈。這裡出現了 CCC ，後面有四個參數，由此可知要填入 `list_for_each_entry_safe` 。 `list_for_each_entry_safe` 可以用來走訪串列中的每一個節點。與只有三個參數的 `list_for_each_entry` 版本比起來， safe 版本，可以把走訪中的節點從 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);
}
```
迴圈中，使用 cmpint 來比大小。若目前走訪的元素 `itm` 比 `pivot` 的數值小，則把它移到 `list_less` 串列中，反之則移進 `list_greater` 串列中。這裡會把節點從一個串列中移到另一個串列。故使用 `list_move` ，即為 DDD 和 EEE 答案。
```graphviz
digraph graphname{
compound=true
rankdir=LR
node[shape=box]
D[label=5]
F[label=7]
B[label=1]
C[label=3]
E[label=2]
pivot[shape=plaintext]
A[label=4]
{
rank=same
pivot->A
}
subgraph {
subgraph cluster_greater {
labeljust=l
label="list_greater"
D->F;
}
subgraph cluster_less {
labeljust=l
label="list_less"
B->C->E;
}
E->D[style=invis]
}
}
```
到目前為止 `list_less` 存放比 `pivot` 小的節點，而 `list_greater` 則存放大於等於 `pivot` 的節點。
---
使用遞迴呼叫 `list_sort` 來對 `list_less` 和 `list_greater` 排序
```c
list_sort(&list_less);
list_sort(&list_greater);
```
```graphviz
digraph graphname{
compound=true
rankdir=LR
node[shape=box]
D[label=5]
F[label=7]
B[label=1]
C[label=3]
E[label=2]
pivot[shape=plaintext]
A[label=4]
{
rank=same
pivot->A
}
subgraph {
subgraph cluster_greater {
labeljust=l
label="list_greater"
D->F;
}
subgraph cluster_less {
labeljust=l
label="list_less"
B->E->C;
}
C->D[style=invis]
}
}
```
---
最後把 `list_less` 、 `pivot` 和 `list_greater` 接回 `head`。其中 `list_greater` 要接到串列中的最後，故用 `list_splice_tail` ，排序即完成
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```
```graphviz
digraph graphname{
compound=true
node[shape=box]
head[shape=plaintext]
pivot[shape=plaintext]
B[label=1]
E[label=2]
C[label=3]
A[label=4]
D[label=5]
F[label=7]
subgraph cluster_0 {
{
rank=same;
B->E->C->A->D->F;
}
}
head->B[lhead=cluster_0]
pivot->A;
}
```
<s>
**解答**
AAA = `struct item`
BBB = `list`
CCC = `list_for_each_entry_safe`
DDD = EEE = `list_move`
FFF = `list_splice_tail`
</s>
> 不用列出參考解答，你著重在程式行為即可。
> :notes: jserv
### 程式的問題
因為是遞迴呼叫，而 quicksort 在最壞的情況下，可能會需要 n 次遞迴呼叫，很容易就會 stack overflow。這時可以用 hybrid sort 解決，解決方式是當深度太深時，可以再用 mergesort 排序。
---
另外這段程式：
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
可以利用 `LIST_HEAD` 巨集，改為
```c
LIST_HEAD(list_less);
LIST_HEAD(list_greater);
```
更為優雅。
### 效能改進方式
:::info
目前這個版本的程式在已經排序好的 linked list ，可能到 $O(n^2)$ worst case 並產生 stack overflow。改進的方法除了成本比較大的 median of medians 外，我比較傾向用隨機挑選 pivot 的方式。
**TODO** 實作此改進
:::
### Hybrid Sort 實作
:::info
**TODO**
目前打算用 quicksort + mergesort + insertion sort
:::
### 對 Linux kernel 貢獻 (移植 Timsort)
目前希望能開發基於 Timsort 的變種。因為 Timsort 是針對陣列排序開發的，故可在裡面使用 binary search 等需要 random access 的演算法。我打算修改 Timsort 演算法讓它適用於 Linux 風格的 doubly-linked list 。初步閱讀 Timsort 文章，感覺有機會加速 Linux kernel doubly-linked list 在 common case (即 list 中有些東西是排序好的) 下的排序速度。
Timsort 是基於 insertion sort + merge sort 再加上一些獨特排序技巧。
這個演算法預期會用非遞迴方式實作。
Timsort 參考資料:
- [最新版本 Timsort](https://github.com/python/cpython/blob/main/Objects/listsort.txt)
- 裡面使用 powersort 的策略來決定是否 merge
- [較舊版本 Timsort](https://github.com/python/cpython/blob/24e5ad4689de9adc8e4a7d8c08fe400dcea668e6/Objects/listsort.txt)
- 相關 merge bug:
- [GitHub Bug](https://github.com/python/cpython/issues/67703)
- [Blog Post](http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/)
- [Python 選擇 merge 策略討論](https://bugs.python.org/issue34561) ([GitHub](https://github.com/python/cpython/issues/78742))
- [不同 merge 策略](https://arxiv.org/pdf/1801.04641.pdf)
由於 powersort 的 merge 策略較難理解，會先用舊版本實作後，再來研究 powersort 。
另外因為這幾種 merge 策略都需要知道每一個 run 長度，有二種方法解決：
- 用額外空間儲存
- 存在 prev pointer 上
:::info
**TODO** 補完 Timsort 說明和程式實作。實驗後，若有正面效益，再進行 Linux kernel 貢獻
> 期待！
:::
之後的研究結果會放在這裡： [Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort)
---
## 測驗2
:::info
**TODO** 我還不熟悉用 Graphviz ，所以這題先沒放圖，之後再補
:::
這裡跟第一題一樣，如果 list 是空的或只有一個元素，就不用排序，直接 return 。
```c
if (list_empty(head) || list_is_singular(head))
return;
```
宣告 stack ，裡面是存放尚未排序完成的串列。並將其用 `INIT_LIST_HEAD` 初始化。 `top` 是存放 stack 頂端的 index 。
之後再用 `list_splice_init` 把 `head` 裡面的東西移進 stack 。故現在 stack 包含一個未排序的 list 。
```c
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]);
```
宣告等一下迴圈中，正在處理當中的 list 。迴圈一開始會把 stack top 上的 list 放入 partition 中。
```c
struct list_head partition;
INIT_LIST_HEAD(&partition);
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
先來看當未排序 list (`partition`) 有二個以上元素的程式。
在這裡跟測驗 1 很像，先宣告 `list_less` 和 `list_greater` ，分別存放比 pivot 小和比 pivot 大的元素。
```c
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);
```
---
把 `pivot` 設為 `partition` 中的第一個元素，並把 `pivot` 從 list 中移除。
```c
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
```
這裡跟測驗 1 一樣，走訪每一個元素，把比 pivot 大的元素放到 `list_greater` ，把比 pivot 小的元素放到 `list_less` 。而 GGGG 也跟測驗 1 一樣是 `list_for_each_entry_safe` ，會用 safe 的版本是因為過程中，走訪中的元素會被移走。
```c
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);
}
```
到目前為址，`list_less` 會存放比 pivot 小的節點， `list_greater` 會存放大於等於 pivot 的節點。
接下來把 pivot 移到 `list_less` 串列的末端(因為 pivot 比 `list_less` 每一個元素都大。因為要移到末端，故要用 `list_move_tail` ，即為 HHHH 的答案。
```c
HHHH (&pivot->list, &list_less);
```
因為 `list_less` 和 `list_greater` 都是未排好的 list ，要把它放到 stack 中，並且把小的放在大的上面。因為是要推入 stack 中，故 IIII 和 JJJJ 都是 `&stack[++top]` 。
```c
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
list_splice_tail(&list_less, JJJJ);
```
接下來看看如果 `partition` 只有一個元素要怎麼處理。特別註意的是，在剛才的程式中，如果 list 是空，就不會被放進 stack ，故 stack 中的 list 一定不為空，所以 `partition` 在 else 裡面一定是只有一個元素的 list。
首先，先把 `partition` 放回 stack 。這裡會放回 stack ，是因為等一下的 while 迴圈會從 stack 中一個個取出元素來處理 stack 中的內容。
```c
} else {
top++;
list_splice_tail(&partition, &stack[top]);
```
這裡的 while 迴圈會不斷地從 stack 頂端的 list 取出元素，把它接在 `head` 的後面，直到 stack 為空或 stack 頂端的 list 不是只有一個元素為止。 在前面的程式，我們知道放進 stack 的順序是由大到小，故這裡取出元素是由小到大，也因為這樣，所以把他們往 `head` 後面排，剛好會是正確的順序由小到大。
這裡的 KKKK 比較 tricky 一點。其實用 `list_del` 把 stack top 上的 list 元素移除後，它應該就是空了。所以不用再初始化一次，但因為題目這樣子出，且我們發現 `top` 在這裡尚未因把 stack 元素取出而減 1 ，故這裡可以填 `&stack[top--]` 。
```c
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 內的 list 具有下面性質：
- 每一個 list 均有一個以上的元素，即非空 list
- stack 上層的 list 內元素的數值，都會比 stack 下層的 list 元素的數值還小。故由上往下放回 `head` 是就會是排好的順序。
- stack 上的元素都一定比已經排好放在 `head` 內的元素還小。
### 程式問題及可優化之處
#### Buffer Overflow 問題
這段程式最大的問題跟測驗 1 類似， quicksort 在最壞的情況下可能讓 stack 大小不夠用，就會出現 buffer overflow 。
#### 善用 `LIST_HEAD` 巨集
這裡如同測驗 1 ，可改用 `LIST_HEAD` 巨集。
```c
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
改寫成
```c
LIST_HEAD(list_less);
LIST_HEAD(list_greater);
```
#### 移動 `partition` 至迴圈內
`partition` 只在迴圈內用到，可把 `partition` 的部份可以移至迴圈內，並使用 `LIST_HEAD` 改寫，成為
```c
LIST_HEAD(partition);
```
### `pivot` 直接移到 `list_less` 內
我們可以把 `pivot` 從 `partition` 移除，最後再移到 `list_less` 。這裡就可以直接移到 `list_less` 內。即把
```c
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);
```
改成
```c
list_move(&pivot->list, &list_less);
```
並且把後面的 `HHHH (&pivot->list, &list_less);` 刪除。
#### 簡化迴圈內的 if
if 內的條件式中，因為 stack 內每一個 list 都一定有一個以上的元素。故可簡化：
```c
if (!list_empty(&partition) && !list_is_singular(&partition)) {
```
可改為
```c
if (!list_is_singular(&partition)) {
```
#### 簡化當 `partition` 只有一個元素時的情況
另外在 else 裡面，又多了一層迴圈。但實際上也是不斷的從 stack 中取出 list 放到 `head` 裡。故 else body 直接用 `list_move_tail` 把從 stack 取出來的 list 中唯一的元素放到 `head` 內即可。整個 else body 可改為
```c
list_move_tail(partition.next, head);
```
#### 減少程式深度
經過上面的簡化， else 內只剩下一個 statement ，故改用 early continue 的方式，把原本 if body 拿到外面，而 if statement 改為
```c
if (list_is_singular(&partition)) {
list_move_tail(partition.next, head);
continue;
}
```
因為這部份的改寫比較複雜，建議直接看下一節的程式碼。
### 程式改寫優化
跟據上面的優化，可以更加優雅
```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 = 0;
list_splice_init(head, &stack[top]);
while (top >= 0) {
LIST_HEAD(partition);
list_splice_init(&stack[top--], &partition);
if (list_is_singular(&partition)) {
list_move_tail(partition.next, head);
continue;
}
LIST_HEAD(list_less);
LIST_HEAD(list_greater);
struct item *pivot =
list_first_entry(&partition, struct item, list);
list_move(pivot, &list_less);
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe (itm, is, &partition, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
}
}
```
### 不依頼 `MAX_DEPTH` 解決方案
上面的改寫，仍擺脫不了 `MAX_DEPTH` 的問題。我們觀察到每一個 `struct list_head` 都有二個指標 `next` 和 `prev` 。若我們仿造 Linux Kernel 內的 `list_sort.c` ，把 list 改為 singly-linked list ，這樣子空下來的指標 `prev` 就可以用來實作 stack 。但缺點是，因為排序的過程中， linked list 就不是原本的 doubly-linked list ，故原本可以優雅得用 `list.h` 裡的巨集，可能很多地方就不適用。
以下的程式實作上述想法，並目改用 Linux kernel 風格的 `list_sort` 函式。
```c
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
if (list_empty(head) || list_is_singular(head))
return;
/* The stack top */
struct list_head *top = head->next;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
top->prev = NULL;
INIT_LIST_HEAD(head);
while (top) {
/* Pop from the stack */
struct list_head *pivot = top;
top = top->prev;
if (!pivot->next) {
list_add_tail(pivot, head);
continue;
}
struct list_head *less = NULL, *greater = pivot->next;
struct list_head **indirect = &greater;
struct list_head **tail = &less;
pivot->next = NULL;
/* Walk through the list and partition */
while (*indirect) {
struct list_head *node = *indirect;
if (cmp(priv, pivot, node) <= 0) {
indirect = &(*indirect)->next;
continue;
}
/* Move to less list */
*indirect = node->next;
*tail = node;
node->next = NULL;
tail = &node->next;
}
/* Put pivot at the end of less list */
*tail = pivot;
/* Push greater and less list into stack */
if (greater) {
greater->prev = top;
less->prev = greater;
top = less;
} else {
less->prev = top;
top = less;
}
}
}
```
:::info
目前這個版本的程式在已經排序好的 linked list ，可能到 $O(n^2)$ 的 worst case 。
改進的方法：除了成本比較大的 median of medians 外，我比較傾向用隨機挑選 pivot 的方式。
除此之外，再加入 fat pivot ，來改善全部節點都是相等的情況。 另外隨機選 pivot 希望還是能保持穩定排序的特性。
**TODO** 實作此改進
:::
### Hybrid Sort 混合排序
:::info
**TODO** 基於 quicksort + mergesort + insertion sort 來開發。
:::
## 測驗1與測驗2實驗數據
以下為實驗數據。測試方式是隨機產生 10000 個 `struct item` 測資，用指定方式排序，量測所花費的 CPU cycle 數。每一項排序演算法均實驗 100 次。實驗結果如下：
| 排序演算法 | 結果 (cycle 數) | 說明 |
| ---------------- | ---------------:| ------------------------------- |
| 測驗1 | 2113507.71 | 題目原始遞迴版演算法 |
| 測驗2 | 3852102.95 | 題目原始非遞迴版演算法 |
| 測驗2改進1 | 2358003.45 | 不依賴 `MAX_DEPTH` 演算法 |
| Kernel list_sort | 1823407.13 | Linux 核心的 `list_sort` 演算法 |
為了讓實驗結果更準確，原始題目的演算法都改為需傳入 `list_cmp_func_t` 比較函式的，並透過傳入的比較函式進行數值比較。
[實驗所用程式碼](https://github.com/yanjiew1/linux23q1-quiz1)
---
## 測驗3
:::info
Graphviz 圖片之後再補上
:::
### 資料結構解釋
xor linked list 主要由二個結構體組成，分別是 `xor_list_t` 和 `xor_note_t` 。`xor_list_t` 是 xor linked list 的主要結構體，會用它來表示一個 xor linked list 。而 `xor_note_t` 則是各個節點的結構體。
`xor_node_t` 是用來表示節點的結構體，其 `cmp` 成員變數是上一個節點位址和下一個節點位址的 xor 運算結構。
`xor_list_t` 中嵌入了二個 `xor_note_t` ，分別是 `head` 和 `tail` ，其分別是放在 xor linked list 開頭的節點，不放置使用者資料 (以下簡稱 head 節點)；而 `tail` 則是放在 xor linked list 結尾的結點，一樣也不放置使用者資料 (以下簡稱 tail 節點）。`xor_list_t` 另一個成員變數 `count` 則會放置整個 xor linked list 的節點數量（不包含不放置使用者資料的 `head` 和 `tail` 節點）
```c
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;
```
在初始化 `xor_list_t` 時， `count` 會被設為 0 ， `head.cmp` 會被設為第一個有放置使用者節點的位址，若串列為空，則直接指向 tail 節點。 `tail.cmp` 會被設為最後一個有放置使用者節點的位址，若串列為空，則直接指向 head 節點。
節點走訪時，我們除了需要知道目前節點的位址外，還需要上一個節點的位址。如此一來，可以透過計算目前節點的 `cmp` 值和上一個節點的記憶體位址的 xor 結果，即可得知下一個節點的位址。
其原理是透過 xor 的特性： `A ^ B ^ B = A` ，即由 xor 組成的運算式，同樣的數值 xor 二次會被抵消掉。
:::info
我覺得 `cmp` 用指標不是很好。二個記憶體位址進行 xor 後的結果就已經不是指向一個有效的記憶體位址，不該再用指標來存。我覺得可以多定義一個型別 `typedef uintptr_t xorlist_cmp_t;` 來區分比較好。
:::
### 巨集和相關函式
`XOR_COMP` 巨集，會把 `a` 和 `b` 二個 `xor_node_t` 指標記憶體位址進行 xor 運算再回傳運算結果。但因為在 C 語言內，指標不能進行 xor 運算，故要先轉型為 `uintptr_t` ，它是一個無號整數，其大小足以儲存指標內的記憶體位址。運算完成後，再轉型回 `xor_note_t` 。
```c
#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))
```
`address_of` 函式用來取得前一個節點或下一個節點的記憶體位址，基本上就是 xor 運算。`n1` 和 `n2` 其中一個放 `xor_node_t` 中的 `cmp` 變數，另一個放前一個節點的位址來取得下一節點的位址或放下一個節點的位址來取得前一個節點的位址。
```c
static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
assert(n1 && n2);
return XOR_COMP(n1, n2);
}
```
跟 Linux kernel 中的 `container_of` 作用一樣。結定一個 struct 內成員的指標 `ptr` 、 struct 本身的型別 `type` 和 struct 裡面成員變數的名稱 `member` ，即可取得該 struct 本身的指標。
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
例如：
```c
typedef struct test_struct {
int a;
struct list_head list;
} test_t;
```
假設有一個指標 `struct list_head *ptr`，指向 `test_t` 結構內的 `list` 。
若要取得指向 `test_t` 的指標，可以用 `container_of(ptr, test_t, list)` 。
可參考[Linux 核心原始程式碼巨集: `container_of`](https://hackmd.io/@sysprog/linux-macro-containerof)
`xorlist_for_each` 此巨集可用來走訪 xor linked list 的每一個節點。此功能跟 `list.h` 內的 `list_for_each_` 一樣。 `node` 是目前走訪的節點， `rp` 會存放下一個節點的位址，而 `rn` 是暫存用變數，在每一回合結束，要計算下個節點時，用來協助暫放下一個節點的位址。
其運作原理是：
- 在 for 迴圈要進入時，會把 head 節點指定給 `rp` （`rp = &(list)->head`)，而 `node` 則指定給 `head` 節點的下一個節點。
- 每次要執行一回合時，會透過 `rp` 上一個節點的位址跟 `node->cmp` 做運算，得到下一個節點的位址，先暫存到 `rn` 中，然後讓 `rp` 指向目前節點，`node` 指向下個節點 (即直接把剛才算好的 `rn` 指定給 `node`) 。透過這樣子操作，讓 `rp` 和 `node` 都前進一個節點。
- `node != &(list)->tail` 這是判斷是否要執行接下來迴圈的判斷式。即當 `node` 還沒有到達 tail 節點時，都會一直走訪下去。
這個迴圈執行過程中，都會保持 `node` 是指向目前走訪的節點；`rp` 是指向上一個節點。
```c
#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)
```
`xorlist_for_each_prev` 跟 `xorlist_for_each` 一樣，只差在是從串列最後一個節點走訪到第一個節點。故不再多作解釋。
```c
#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)
```
`xorlist_for_each_from` 巨集用來從某個特定節點開始走訪到最後一個節點。`pos1` 要傳入要開始走訪節點的上一個節點， `pos2` 要傳入要走訪的節點。 `rp` ， `rn` 均為暫存變數，`rp` 會保留上一個節點的指標，`rn` 則會在計算下一個節點位址時被使用。
```c
#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)
```
`xorlist_for_each_from_prev` 跟前一個巨集很像，只是差在從某節節點由後往前走訪，`pos1` 要指向要走訪節點的後一個節點。
```c
#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)
```
`xorlist_delete_prototype` 和 `xorlist_delete_call` 可以用來協助定義和使用刪除節點用的函式，此函式要放置釋放記憶體空間相關的程式，會由後面要講解的 `xorlist_del` 呼叫。
因為 xor linked list 本身是嵌入在節點內部的節構，其相關操作函式不會知道 xor linked list 的使用者，要如何配置記憶體及釋放記憶體。故這二個巨集用來協助使用者寫出符合 xor linked list 用的釋放記憶體函式。
```c
/* 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
```
---
`xornode_init` 、 `XORNODE_INIT` 都是用來初始化節點 (`xor_node_t`)。其中 `xornode_init` 是以函式的形式實作，而 `XORNODE_INIT` 是以巨集的方式實作。其功能都是把節點的 `cmp` 成員函數設為 `NULL` 。
```c
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)
```
用來初始化 `xor_list_t` （用來表示串列的主要資料結構）的巨集。從這裡可以觀查到，一個新的沒有存放節點的串列，會把 head 節點的 `cmp` 成員變數指向 tail 節點，代表 head 節點下一個節點就是 tail 節點；也把 tail 節點的 `cmp` 成員變數指向 head 節點，代表 tail 節點的上一個節點就是 head 節點。
```c
#define XORLIST_INIT(h) \
do { \
(h).head.cmp = &(h).tail; \
(h).tail.cmp = &(h).head; \
(h).count = 0; \
} while (0)
```
---
`xorlist_add` 把節點 `n` 加入到 `list` 開頭。
`real_prev` 和 `real_next` 為分別指向上一個節點和下一個節點的指標。
一開始先設定 `real_prev` 和 `real_next` 的位址。因為 `xorlist_add` 要把 `n` 加入到 `list` 開頭。故 `n` 的上一個節點會是 head 節點，故就直接把 head 節點的位址指定給 `real_prev` ，而 `real_next` 則跟據 `list` 是否為空，來決定要設定為 `real_prev->cmp` 或 tail 節點。
:::info
這裡其實不用這麼麻煩，因為 list 為空時 head 節點內的 `cmp` 就會是 tail 節點。
:::
最後再計算和更新 `real_prev`, `real_next` 和 `p` 的 `cmp` 值。
- 我們知道 head 節點的 `cmp` 會指向第一個節點，故直接把其 `cmp` 值更新為 `n`。
- 要加入的節點 `n` 其 `cmp` ， 按照 xor linked list 定義，就是前一個節點和下一個節點的 xor 結果，故 `n->cmp = XOR_COMP(real_prev, real_next)` 。
- 設定 `real_next->cmp` 時，要把取得 `real_next` 的下一個節點的位址 `XOR_COMP(real_prev, real_next->cmp)` ，再和目前節點做 xor 運算 `XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp))` 。
- 最後因為加入了一個新節點，故 `count` 要加 1
```c
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 = &list->tail;
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;
}
```
簡化版但又好理解的程式
```c
int xorlist_add(xor_list_t *list, xor_node_t *n)
{
if (!n)
return ENOMEM;
xor_node_t *real_prev = &list->head;
xor_node_t *real_next = real_prev->cmp;
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;
}
```
`xorlist_del` ： 給定要刪除節點的前一個節點 `n` 、要刪除的節點 `target` 和節點記憶體釋放的函式 `delete_func` 來刪除節點。
前面二個 assert ，是確保 `list`, `n`, `target`, `delete_func` 都不為 `NULL` 。以及 要刪除節點不能是 head 節點和 tail 節點。
這個函式的變數命名相較於 `xorlist_add` 很不友善。但從程式的邏輯可以推出各個變數的功能：
- `nn` 為 `target` 和 `n->cmp` 的 xor 結果，故它應為上上一個節點的位址
- `an` 為 `n` 和 `target->cmp` 的 xor 結果，故它應為下一個節點的位址
- `ana` 為 `an->cmp` 和 `target` 的 xor 結果，故它應為下下一個節點的位址
因為要刪除 `target` 節點，故其前後節點(`n` 和 `an`)的 `cmp` 都要進行修改。
- `n->cmp = XOR_COMP(nn, an);` 上一個節點的 `cmp` 改為上上一個節點的位址與下一個節點的位址 xor 的結果
- `an->cmp = XOR_COMP(n, ana);` 下一個節點的 `cmp` 改為下下一個節點的位址與上一個節點的位址 xor 的結果
最後把節點記憶體釋放 `delete_func(target);` ， 也把 `count` 減 1 。
```c
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;
}
```
:::info
雖然這個函式裡面變數命名不好，但會這樣子命名，可能是因為它考慮到 `n` 傳入 `target` 的下一個節點也可以運作正常的特性來命名。但或許它仍需要有更好的名字。
另外，雖然這個函式是把節點移除，但節點之後可能可以用到其他地方，故我覺得在這裡就要釋放記憶體反而限縮了它的應用。
另一個問題是呼叫 `delete_func` 沒有檢查記憶體釋放是否成功。這和後面的 `xorlist_destroy` 函式有進行檢查刪除是否成功形成對比。
:::
<s>如果是我，</s> 我會這樣改進：
```c
void xorlist_del(xor_list_t *list,
xor_node_t *prev,
xor_node_t *target)
{
assert(list && n && target);
assert(&list->head != target && &list->tail != target);
xor_node_t *pprev = address_of(target, n->cmp);
xor_node_t *next = address_of(n, target->cmp);
xor_node_t *nnext = address_of(target, next->cmp);
prev->cmp = XOR_COMP(pprev, next);
next->cmp = XOR_COMP(prev, nnext);
list->count--;
}
```
這個函式不需要傳入 `delete_func` ，釋放記憶體的工作就交給 caller 來做。
`xorlist_destroy` 把整個 xor linked list 刪除，此函數實作錯誤。
一開始先確保 delete_func 不為空。
```c
assert(delete_func);
```
接下來宣告和設定此函數內變數的初始值。 `real_prev` 是目前走訪節點的上一個節點，設定為 head 節點。 `node` 為目前走訪的節點，設定為第一個節點。 `real_prev` 為目前走訪節點的下一個節點，設定為 `node` 的下一個節點。
```c
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;
```
以下程式在進入迴圈前，會把 `preal_prev` 和 `node` 各往前走訪一個節點。因此在這段程式執行完後， `real_prev` 指向第一個節點，`node` 指向第一個節點的下一個節點
```c
real_prev = node;
node = real_next;
```
以下程式走訪每一個節點，並刪除每一個節點。迴圈內前面四行會先把 `real_prev` 和 `node` 都先指向下一個節點，原本的 `real_prev` 暫存在 `tmp` 中，最後再把 `tmp` 刪除。
```c
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");
}
```
這段程式很明顯實作錯誤。在 while 迴圈走訪時，每次都是刪除 `node` 的前一個節點。而最後在 `node` 為 tail 節點時，就不會進入迴圈了。故最後一個節點的空間無法被釋放。
改進如下：
```c
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 *tmp, *real_next;
while (node != &list->tail) {
real_next = address_of(real_prev, node->cmp);
tmp = node;
real_prev = node;
node = real_next;
if (delete_func(tmp) != 0)
perror("delete function failed");
}
return 0;
}
```
與原本題目不同時，每次刪除的節點不是 `real_prev` 而且目前走訪的節點 `node`。且 `node` 在這段程式確實會從第一個節點走訪到最後一個節點，故可以確保每個節點都刪除。
接下來的程式為測試上述 xor linked list 的程式碼。
以下為測試用的`struct test_node` 結構體。有二個成員變數，分別是 `value` 和 `xornode` 。`xornode` 就是用來讓此結構體可以串接在 xor linked list 。
```c
struct test_node {
int value;
xor_node_t xornode;
};
```
透過 `xorlist_delete_prototype` 巨集來宣告刪除節點用的函式。
```c
xorlist_delete_prototype(test_delete, _node)
{
struct test_node *node = container_of(_node, struct test_node, xornode);
free(node);
return 0;
}
```
分析 `main` 內的函數。先看裡頭宣告的變數：
- `xor_list_t list;` 宣告一個 xor linked list
- `xor_node_t *p1, *p2;`: `p1` 和 `p2` 為等一下測試時，放置倒數第 6 (i=5)和第 7 (i=6)個節點。
- `xor_node_t *real_prev, *real_next, *node;`: `node` 為等一下走訪時，表示正在走訪的節點。 而 `real_prev` 和 `real_next` 均為等一下走訪時的暫存變數。
以下為加入測試資料的程式碼：
```c
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;
}
```
上述程式碼中，`XORLIST_INIT` 巨集用來初始化 `list` 這一個 `xor_list_t` 結構。
迴圈內則透過 `malloc` 來配置新節點記憶體，用 `xornode_init` 來初始化新節點 （把 `cmp` 設成 0）。並且設定節點的 `value` 值 `new->value = i;` ，再將節點加入串列 `xorlist_add(&list, &new->xornode);` 。另外特別把 `p1` 設成倒數第 6 個節點和倒數第 7 個節點。
上述程式碼執行完成後，串列內的值從最前面節點由 999 倒數至最後面節點 0 。
接下來就是測試 `xorlist_for_each` 、 `xorlist_for_each_from` 、`xorlist_for_each_from_prev` 、 `xorlist_for_each_prev` 這四個走訪節點的巨集，其型式和程式碼都很簡單。裡面就是單純把節點的值輸出而已。比較可以注意的是這裡特別用 `container_of(node, struct test_node, xornode)` 巨集，讓我們可以從指向 `struct test_node` 結構體內 `xornode` 的指標，取得指向 `struct test_node` 結構體的指標。
最後再走訪一次每一個節點，用 `xorlist_del` 刪除每一個節點後，再用 `xorlist_destroy` 把整個 list 刪除。 但最後的 `xorlist_destroy` 有點多餘，因為前面已經把每一個節點都刪除，記憶體都釋放了。
Sign in with Wallet
Connect another wallet