# 2023q1 Homework1 (quiz1)
contributed by < [Welly0902](https://github.com/Welly0902) >
## 測驗一
**延伸問題**
- [x] 解釋程式碼運作原理
- [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] ==BONUS==: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
---
Circular doubly-linked list 節點 structure 定義如下：
```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;
}
```
可看到 `cmpint` 並不是直接 `return *p1 - *p2;`，故接下來會觀察一下 `uint16_t` 這個資料型態是否有它必要的意義。
再來看一下 sorting 的程式：
```c
static void list_sort(struct list_head *head)
{
//1
if (list_empty(head) || list_is_singular(head))
return;
//2
struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
//3 AAA BBB
struct item *pivot = list_first_entry(head, item, list);
list_del(&pivot->list);
//4
struct item *itm = NULL, *is = NULL;
// CCC
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
// DDD
list_move_tail (&itm->list, &list_less);
else
// EEE
list_move_tail (&itm->list, &list_greater);
}
//5
list_sort(&list_less);
list_sort(&list_greater);
//6
list_add(&pivot->list, head);
list_splice(&list_less, head);
// FFF
list_splice_tail(&list_greater, head);
}
```
一段一段拆解來看，首先：
```c
if (list_empty(head) || list_is_singular(head))
return;
```
參照 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 說明，我們可以看到`list_empty`的程式碼：
```c
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
return `1` 代表 list 是空的，也就是說的 `head->next == head` 時 list 是空的，這裡我不太確定 circular doubly-linked list 當一開始空的時候長怎樣，所以我們回去看 `list.h` 中的 `INIT_LIST_HEAD`：
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
畫成圖為：
```graphviz
digraph g {
rankdir=LR;
node [shape=record, colorscheme=reds9];
head [label="{<ref1> prev | <data> head | <ref2> next}"];
head:ref2 -> head:data:n;
head:ref1 -> head:data:s;
}
```
所以從上圖我們可看出 `head->next == head` 確實為只有 head 的初始狀態，為空。
接下來看一下 `list_is_singular` function，同樣查看 `list.h` 了解它的目的是為了去檢驗是否剛好只有一個節點在此。看一下下方程式碼:
```c
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
可看條件為非空且 `head->prev` 與 `head->next` 指到同一個 node。
```graphviz
digraph g {
rankdir=LR;
node [shape=record, colorscheme=reds9];
head [label="{<ref1> prev | <data> head | <ref2> next}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
head:ref2 -> a:data:n;
head:ref1 -> a:data:s;
}
```
```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]
}
}
```
所以回到 sorting 原程式，`//1` 先檢查如果 input list 為空或只有一個節點，那直接回傳即為排列好的 list。再來 `//2` 的部分 initialize 了兩個 pointer `list_less` 和 `list_greater`:
```graphviz
digraph g {
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}", color=6];
h2 [label="{<ref1> | <data> list_greater | <ref2>}",color=6];
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h1:ref2 -> h1:data:n [color=red];
h1:ref1 -> h1:data:s [color=red];
h2:ref2 -> h2:data:n [color=red];
h2:ref1 -> h2:data:s [color=red];
}
}
```
再來 `//3` 的部分首先先看 `list_first_entry` macro 的程式碼:
```c
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
可以看到運用了另一個 macro `list_entry`:
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
裡面又連結到另一個 `list.h` 中的 macro `container_of`，並根據 [ifdef, ifndef](https://docs.revenera.com/installshield26helplib/LangRef/Langrefifdef_and_ifndef.htm#:~:text=Use%20the%20%23ifdef%20statement%20when,expression%20has%20not%20been%20defined.) 定義加上 indentation 以方便閱讀:
```c
#ifndef container_of
#ifdef __LIST_HAVE_TYPEOF
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#else
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
#endif
#endif
```
對於 `__LIST_HAVE_TYPEOF` 檢查是否允許 GNUC extension 有關條件的說明可參考[之前同學](https://hackmd.io/@RinHizakura/HkEuhNwGO)的說明。這裡直接看
* 延伸閱讀: [為何需要 char * casting](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel)、[macro container_of explained](https://psomas.wordpress.com/2009/07/01/weird-kernel-macros-container_of/)、[kobject 基礎介紹](https://medium.com/powerof2/the-kernel-kobject-device-model-explained-89d02350fa03)
而這裡透過詢問 chatgpt，可快速了解 `container_of` macro 所代表的意義
> Q: container_of in linux kernel
> ChatGPT: container_of is a powerful and commonly used macro in the Linux kernel that allows a developer to obtain a pointer to a structure containing a given field.
The container_of macro takes three arguments: a pointer to a field in a structure, the name of the structure containing the field, and the name of the field itself. The macro then computes the offset of the field within the structure and returns a pointer to the containing structure.
:::
所以我們可知 `list_entry` 可讓我們得到一個 member pointer 用來取用目前 pointer 指向節點內的 member，以取用節點內 member進行操作。而`list_first_entry` 則可得到指向目前 linked list 中第一個節點的 mpointer 來對其進行操作。
回到 `//3` 的程式碼，從說明可以快速推出 AAA 與 BBB 為 `item` 和 `list`。
```c
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
```
再來看程式碼:
```c
//3 AAA BBB
struct item *pivot = list_first_entry(head, item, list);
list_del(&pivot->list);
```
首先第一行:
```graphviz
digraph g {
label="list_entry((head)->next, item, list)"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n [color=red]
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
再來第二行的 `list_del` 程式碼如下:
```c
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
> LIST_POISONING can be enabled during build-time to provoke an invalid memory
access when the memory behind the next/prev pointer is used after a list_del.
This only works on systems which prohibit access to the predefined memory addresses.
這裡做 deletion 是為了先將選中的 pivot (此程式是選 list 的第一個元素當作 pivot) 當作分隔 list 中 node 的 i 值大小的依據。Deletion 過程如下圖:
```graphviz
digraph g {
label="struct list_head *next = node->next;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h4 [shape=plaintext, label="next", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n
h4:n -> b:n [color=red]
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
```graphviz
digraph g {
label="struct list_head *prev = node->prev;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h4 [shape=plaintext, label="next", fontname="Arial"]
h5 [shape=plaintext, label="prev", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n
h4:n -> b:n
h5:n -> c:n [color=red]
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
```graphviz
digraph g {
label="next->prev = prev;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h4 [shape=plaintext, label="next", fontname="Arial"]
h5 [shape=plaintext, label="prev", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> a:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n
h4:n -> b:n
h5:n -> c:n
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
```graphviz
digraph g {
label="prev->next = next;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h4 [shape=plaintext, label="next", fontname="Arial"]
h5 [shape=plaintext, label="prev", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red];
h0:ref2:c -> a:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n
h4:n -> b:n
h5:n -> c:n
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
由上圖可以看出 n2 及 n3 經過 pivot 指向的 node n1 deletion 後已經成為
一個 circular doubly-linked list，不過從此處程式碼看不出:
1. n1 節點剩餘 link 的處理
2. list head 也沒有重新指到新的頭尾
這兩個問題暫時還沒找到解答。
再來先繼續往下看主程式:
```c
//4
struct item *itm = NULL, *is = NULL;
// CCC
list_for_each_entry_safe (itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
// DDD
list_move_tail (&itm->list, &list_less);
else
// EEE
list_move_tail (&itm->list, &list_greater);
}
```
首先先建立等等 for each 會用到的 member pointer:
```graphviz
digraph g {
label="struct item *itm = NULL, *is = NULL;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
h6 [shape=circle, label=itm, color=6]
h7 [shape=circle, label=is, color=6]
h8 [shape=plaintext, label="null", fontname="Arial"]
h9 [shape=plaintext, label="null", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> n1 | <ref2>}"];
b [label="{<ref1> | <data> n2 | <ref2>}"];
c [label="{<ref1> | <data> n3 | <ref2>}"];
subgraph {
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h0:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h5:n -> c:n;
h6 -> h8;
h7 -> h9;
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
接下來先看一下 `list_move_tail` 的程式:
```c
static inline void list_move_tail(struct list_head *node,
struct list_head *head)
{
list_del(node);
list_add_tail(node, head);
}
```
以及 `list_add_tail` 的程式:
```c
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
那我們假設目前的 list 如下圖:
```graphviz
digraph g {
// label="struct item *itm = NULL, *is = NULL;"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
h6 [shape=circle, label=itm]
h7 [shape=circle, label=is]
h8 [shape=plaintext, label="null", fontname="Arial"]
h9 [shape=plaintext, label="null", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h0:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h5:n -> c:n;
h6 -> h8;
h7 -> h9;
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
則當我們利用 `cmpint` 與 pivot相減後，以上圖例子來看，首先`3-6<0`，故會執行`list_move_tail (&itm->list, &list_less);`:
```graphviz
digraph g {
label="list_move_tail (&itm->list, &list_less);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
h6 [shape=circle, label=itm]
h7 [shape=circle, label=is]
h8 [shape=plaintext, label="null", fontname="Arial"]
h9 [shape=plaintext, label="null", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h0:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h5:n -> c:n;
h6 -> h8;
h7 -> h9;
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
}
}
```
先執行 `list_del(&itm->list)`(當下節點為 3):
```graphviz
digraph g {
label="list_del(&itm->list);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
h6 [shape=circle, label=itm]
h7 [shape=circle, label=is]
h8 [shape=plaintext, label="null", fontname="Arial"]
h9 [shape=plaintext, label="null", fontname="Arial"]
h10 [shape=plaintext, label="node", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}", color=6];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// b:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// b:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
c:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h0:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h5:n -> c:n;
h6 -> h8;
h7 -> h9;
h1:ref2 -> h1:data:n;
h1:ref1 -> h1:data:s;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
h10 -> b:data [color=red];
}
}
```
接著 `list_add_tail(&itm->list, &list_less)`:
```graphviz
digraph g {
label="list_add_tail(&itm->list, &list_less);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
h6 [shape=circle, label=itm]
h7 [shape=circle, label=is]
h8 [shape=plaintext, label="null", fontname="Arial"]
h9 [shape=plaintext, label="null", fontname="Arial"]
h10 [shape=plaintext, label="node", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h1:ref2 -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//1"];
b:ref2:c -> h1:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//2"];
h1:ref1:c -> b:data:w[weight = 100, style = invis];
b:ref1:c -> h1:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//3"];
h1:ref1 -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//4"];
c:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// c:ref1:c -> b:data:w[weight = 100, style = invis];
// b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
c:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
h0:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h5:n -> c:n;
h6 -> h8;
h7 -> h9;
h2:ref2 -> h2:data:n;
h2:ref1 -> h2:data:s;
h10 -> b:data;
}
}
```
當執行完 主程式的 `//4`，可得下圖:
```graphviz
digraph g {
// label="list_add_tail(&itm->list, &list_less);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
// h4 [shape=plaintext, label="next", fontname="Arial"]
// h5 [shape=plaintext, label="prev", fontname="Arial"]
// h10 [shape=plaintext, label="node", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
h1 -> b [dir=both]
h2 -> c [dir=both]
// a:ref2:c -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// h1:ref2 -> b:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//1"];
// b:ref2:c -> h1:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//2"];
// h1:ref1:c -> b:data:w[weight = 100, style = invis];
// b:ref1:c -> h1:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//3"];
// h1:ref1 -> b:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, color=red, label="//4"];
// c:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// c:ref1:c -> b:data:w[weight = 100, style = invis];
// b:ref1:c -> a:data:w[weight = 100, style = invis];
// a:ref1:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// c:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false];
// h0:ref2:c -> c:data:n [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
// h0:ref1:c -> c:data:s [arrowhead=normal, arrowtail=none, dir=both, tailclip=false, style=dashed];
h3:n -> a:n;
// h4:n -> b:n;
// h2:ref2 -> h2:data:n;
// h2:ref1 -> h2:data:s;
// h10 -> b:data;
}
}
```
接著進行到 `//5` 時，會將 `list_less` 和 `list_greater` 中的值遞迴排序好。
排序好後會剩下 `list_less` 和 `list_greater` 的 list 和 pivot node 並執行 `//6`。
在執行前先看一下 `list_splice` 的程式碼:
```c
static inline void list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *head_first = head->next;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->next = list_first;
list_first->prev = head;
list_last->next = head_first;
head_first->prev = list_last;
}
```
以及 `list_splice_tail` 的程式碼:
```c
static inline void list_splice_tail(struct list_head *list,
struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->prev = list_last;
list_last->next = head;
list_first->prev = head_last;
head_last->next = list_first;
}
```
在 `//6` 中先執行 `list_add(&pivot->list, head)` 將 pivot 加到 head pointer 最前面:
```graphviz
digraph g {
label="list_add(&pivot->list, head);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
h3 [shape=plaintext, label="pivot", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}", color=6];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
h0:c -> a [dir=both]
h1 -> b [dir=both]
h2 -> c [dir=both]
h3 -> a:data;
}
}
```
```graphviz
digraph g {
label="list_splice(&list_less, head);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
// h3 [shape=plaintext, label="pivot", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}", color=6];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// h0:c -> a [dir=both]
h0:c -> b [dir=both, color=red]
h0:ref1:c -> a:ref2:n [dir=both]
b -> a [dir=both, color=red]
h1 -> b [dir=both]
h2 -> c [dir=both]
// h3 -> a:data;
}
}
```
`list_splice_tail` 時從 head->prev 也就是 head 這個 linked list的最後一個節點(6)進行操作:
```graphviz
digraph g {
label="list_splice_tail(&list_greater, head);"
rankdir=LR;
node [shape=record, colorscheme=reds9];
// h3 [shape=plaintext, label="pivot", fontname="Arial"]
h0 [label="{<ref1> | <data> head | <ref2>}"];
a [label="{<ref1> | <data> 6 | <ref2>}"];
h1 [label="{<ref1> | <data> list_less | <ref2>}"];
b [label="{<ref1> | <data> 3 | <ref2>}"];
h2 [label="{<ref1> | <data> list_greater | <ref2>}"];
c [label="{<ref1> | <data> 8 | <ref2>}"];
subgraph {
// h0:c -> a [dir=both]
h0:c -> b [dir=both];
b -> a [dir=both];
h1 -> b [dir=both];
h2 -> c [dir=both];
// h3 -> a:data;
a -> c [dir=both, color=red];
h0:ref1:c -> c:ref2:n [dir=both, color=red]
}
}
```
---
## 測驗二
**延伸問題**
- [ ] 解釋程式碼運作原理
- [ ] 針對 [Quick sort](https://en.wikipedia.org/wiki/Quicksort) 提出程式碼的改進方案並實作
- [ ] 引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
- [ ] ==BONUS==: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
## 測驗三
**延伸問題**
- [ ] 解釋上述程式碼運作原理，指出其實作缺陷並改進
- [ ] 在上述 XOR linked list 的基礎，實作測驗 `1` 和 `2` 提及的快速排序演算法，注意要引入你改進效能的版本
- [ ] 修改 `xorlist_destroy`，使其不急著釋放記憶體，而搭配 [atexit(3)](https://man7.org/linux/man-pages/man3/atexit.3.html) 並在程式即將結束執行時，才批次處理資源釋放
Sign in with Wallet
Connect another wallet