---
# System prepended metadata

title: 2023q1 Homework1 (quiz1)

---

# 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) 並在程式即將結束執行時，才批次處理資源釋放
