# 2024q1 Homework2 (quiz1+2)
contributed by < `jychen0611` >
## [第 1 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1)
### quiz 1
#### <程式運作原理>
結構體
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
以下分別為取得串列尾節點和取得串列長度之函式。
因為 `left` 為節點指標的指標，`(*left)`表指向該節點的指標，依據判斷可知 AAAA 應填入`(*left)->next` ，而 `left = &((*left)->next)` 表`left` 指向隔壁節點指標的位址。
其函式回傳為指向串列尾端節點的指標。
同理，BBBB 應填入`(*left)->next` ，表`left` 指向隔壁節點指標的位址。
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
#### <圖解說明>
```graphviz
digraph g1 {
node[shape=plaintext];
left [fontcolor="brown"];
p0 [fontcolor="black"];
p1 [fontcolor="black"];
p2 [fontcolor="black"];
p3 [fontcolor="black"];
p4 [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
p3 -> n3 -> p1 -> n1 -> p0 -> n0 -> p2 -> n2 -> p4 -> n4 -> l0;
}
left -> p3;
}
```
```graphviz
digraph g2 {
node[shape=plaintext];
left [fontcolor="brown"];
p0 [fontcolor="black"];
p1 [fontcolor="black"];
p2 [fontcolor="black"];
p3 [fontcolor="black"];
p4 [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
p3 -> n3 -> p1 -> n1 -> p0 -> n0 -> p2 -> n2 -> p4 -> n4 -> l0;
}
left -> p1;
}
```
以下是運用 Optimized QuickSort — C Implementation (Non-Recursive) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼。
* begin[i], end[i] 分別用來存放單一排序分割的起始點和終點，i 為分割編號
* left 用來存放小於等於 pivot 的節點
* right 用來存放大於 pivot 的節點
* result 用來存放排序完的分割
其流程為
* 以 L R 指向`串列分割 i` 之兩端，當 L R 尚未交會則進行內部排序
* 最左邊的數設為 pivot，p 則指向 pivot 隔壁的節點，pivot 的 next 指向 NULL
* 指標 p 會一直往右走，將大於 pivot 的節點存入 right ， 小於的存入 left
* 由上述可知 CCCC 應填入 `p -> next`
* 接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2
* 由上述可知 DDDD 應填入 `list_tail(left)` ， EEEE 應填入 `list_tail(right)`
* 下一回合將進行 `串列分割 i+2` 之內部排序（也就是先排右邊）
* 直到右邊都排序完成後，才會將排序完的分割存入 result，並開始進行左邊分割的排序。
```c
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
#### <圖解說明>
```graphviz
digraph g1 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n3 -> n1 -> n0 -> n2 -> n4 -> l0
}
"begin[0]" -> n3;
"end[0]" -> n4;
pivot -> n3;
L -> n3;
R -> n4;
p -> n1;
}
```
```graphviz
digraph g2 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n1 -> n0 -> n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n1;
}
```
```graphviz
digraph g3 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n0 -> n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> n1 -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n0;
}
```
```graphviz
digraph g4 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
n2 -> n4 -> l0
}
pivot -> n3 -> l1;
left -> n1 -> n0 -> l2;
right -> l3;
L -> n3;
R -> n4;
p -> n2;
}
```
```graphviz
digraph g5 {
node[shape=plaintext];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
p [fontcolor="black"];
l0 [label ="NULL", fontcolor="black"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
}
left -> n1 -> n0 -> n2 -> l0;
pivot -> n3 -> l1;
right -> l2;
L -> n3;
R -> n4;
p -> n4;
}
```
```graphviz
digraph g6 {
node[shape=plaintext];
"begin[0]" [fontcolor="brown"];
"end[0]" [fontcolor="brown"];
"begin[1]" [fontcolor="brown"];
"end[1]" [fontcolor="brown"];
"begin[2]" [fontcolor="brown"];
"end[2]" [fontcolor="brown"];
"left" [fontcolor="purple"];
"right" [fontcolor="purple"];
pivot [fontcolor="red"];
L [fontcolor="blue"];
R [fontcolor="blue"];
l1 [label ="NULL", fontcolor="black"];
l2 [label ="NULL", fontcolor="black"];
l3 [label ="NULL", fontcolor="black"];
node[shape=box];
n0 [label= "0"];
n1 [label= "1"];
n2 [label= "2"];
n3 [label= "3"];
n4 [label= "4"];
{
rank="same";
}
"begin[0]" -> n1;
"end[0]" -> n2;
"begin[1]" -> n3;
"end[1]" -> n3;
"begin[2]" -> n4;
"end[2]" -> n4;
pivot -> n3 -> l1;
left -> n1 -> n0 -> n2 -> l3;
right -> n4 -> l2;
L -> n3;
R -> n4;
}
```
### quiz 2
#### <程式運作原理>
以下為 Timsort merge 過程。
由於 tail 為指標的指標，AAAA 應填入 `&head` ，表指標 head 的位址。
同理， BBBB 應該填入 `&a->next` ， CCCC 應該填入 `&b->next` 表指向下個節點指標的位址（更新 tail）。
```c
static struct list_head *merge(void *priv,
list_cmp_func_t cmp,
struct list_head *a,
struct list_head *b)
{
struct list_head *head;
struct list_head **tail = AAAA;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = BBBB;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = CCCC;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
以下為補上雙向鏈結串列中的 `prev` 之函式，過程如下：
* 先將 tail 的 `next` 指向 head
* 以 `list` 逐步走訪整個串列，將 link 所指節點的 `prev` 指向 tail 。
* 最後再補上 tail 的 `next` 指向 head ， head 的 `prev` 指向 tail 之動作
由上述可知 DDDD 為 `tail->next` ，EEEE 為 `head->prev`
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
DDDD = head;
EEEE = tail;
}
```
下面是 timsort 程式碼。其過程如下 ：
```c
void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
stk_size = 0;
struct list_head *list = head->next, *tp = NULL;
if (head == head->prev)
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
do {
/* Find next run */
struct pair result = find_run(priv, list, cmp);
result.head->prev = tp;
tp = result.head;
list = result.next;
stk_size++;
tp = merge_collapse(priv, cmp, tp);
} while (list);
/* End of input; merge together all the runs. */
tp = merge_force_collapse(priv, cmp, tp);
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= FFFF) {
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
}
```
## [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### quiz 1
#### <程式運作原理>
### quiz 2
#### <程式運作原理>
### quiz 3
#### <程式運作原理>
## 參考資料
* [作業說明](https://hackmd.io/@sysprog/BkmmEQCn6)
* [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
* [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
* [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/@sysprog/c-std-security)
* [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
* [Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)
* [Graphviz](https://graphviz.org/)
Sign in with Wallet
Connect another wallet