2023q1 Homework1 (quiz1)

contributed by < yanjiew1 >

GitHub 連結: https://github.com/yanjiew1/linux23q1-quiz1

開發與實驗環境

$ 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 。

if (list_empty(head) || list_is_singular(head))
    return;

接下來看到宣告了 list_less 和　list_greater 還有 pivot 。可知這應該是一個 quick sort 演算法。

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 。

list_first_entry 資訊

以下為 list.h 中的 list_first_entry 巨集內容

/**
 * 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 指向第一個元素

list_del(&pivot->list); 則是把 pivot 從原本在 head 的串列中取下來。故執行 list_del 後，pivot 不再屬於 head指向的 list

接下來即將進入迴圈。這裡出現了 CCC ，後面有四個參數，由此可知要填入 list_for_each_entry_safe 。 list_for_each_entry_safe 可以用來走訪串列中的每一個節點。與只有三個參數的 list_for_each_entry 版本比起來， safe 版本，可以把走訪中的節點從 list 中移除，不影響之後的走訪。

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 答案。

到目前為止 list_less 存放比 pivot 小的節點，而 list_greater 則存放大於等於 pivot 的節點。

使用遞迴呼叫 list_sort 來對 list_less 和 list_greater 排序

list_sort(&list_less);
list_sort(&list_greater);

最後把 list_less 、 pivot 和 list_greater 接回 head。其中 list_greater 要接到串列中的最後，故用 list_splice_tail ，排序即完成

list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);

**解答** AAA = `struct item` BBB = `list` CCC = `list_for_each_entry_safe` DDD = EEE = `list_move` FFF = `list_splice_tail`

不用列出參考解答，你著重在程式行為即可。

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

程式的問題

因為是遞迴呼叫，而 quicksort 在最壞的情況下，可能會需要 n 次遞迴呼叫，很容易就會 stack overflow。這時可以用 hybrid sort 解決，解決方式是當深度太深時，可以再用 mergesort 排序。

另外這段程式：

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

可以利用 LIST_HEAD 巨集，改為

LIST_HEAD(list_less);
LIST_HEAD(list_greater);

更為優雅。

效能改進方式

目前這個版本的程式在已經排序好的 linked list ，可能到

O (n^{2})

worst case 並產生 stack overflow。改進的方法除了成本比較大的 median of medians 外，我比較傾向用隨機挑選 pivot 的方式。

TODO 實作此改進

Hybrid Sort 實作

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
- 裡面使用 powersort 的策略來決定是否 merge
較舊版本 Timsort
- 相關 merge bug:
  - GitHub Bug
  - Blog Post
Python 選擇 merge 策略討論 (GitHub)
不同 merge 策略

由於 powersort 的 merge 策略較難理解，會先用舊版本實作後，再來研究 powersort 。

另外因為這幾種 merge 策略都需要知道每一個 run 長度，有二種方法解決：

用額外空間儲存
存在 prev pointer 上

TODO 補完 Timsort 說明和程式實作。實驗後，若有正面效益，再進行 Linux kernel 貢獻

期待！

之後的研究結果會放在這裡： Timsort 研究與對 Linux 核心貢獻嘗試

測驗2

TODO 我還不熟悉用 Graphviz ，所以這題先沒放圖，之後再補

這裡跟第一題一樣，如果 list 是空的或只有一個元素，就不用排序，直接 return 。

if (list_empty(head) || list_is_singular(head))
    return;

宣告 stack ，裡面是存放尚未排序完成的串列。並將其用 INIT_LIST_HEAD 初始化。 top 是存放 stack 頂端的 index 。

之後再用 list_splice_init 把 head 裡面的東西移進 stack 。故現在 stack 包含一個未排序的 list 。

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 中。

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 大的元素。

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 中移除。

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 的版本是因為過程中，走訪中的元素會被移走。

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 的答案。

HHHH (&pivot->list, &list_less);

因為 list_less 和 list_greater 都是未排好的 list ，要把它放到 stack 中，並且把小的放在大的上面。因為是要推入 stack 中，故 IIII 和 JJJJ 都是 &stack[++top] 。

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 中的內容。

} 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--] 。

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 巨集。

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

改寫成

LIST_HEAD(list_less);
LIST_HEAD(list_greater);

移動 `partition` 至迴圈內

partition 只在迴圈內用到，可把 partition 的部份可以移至迴圈內，並使用 LIST_HEAD 改寫，成為

LIST_HEAD(partition);

`pivot` 直接移到 `list_less` 內

我們可以把 pivot 從 partition 移除，最後再移到 list_less 。這裡就可以直接移到 list_less 內。即把

list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);

改成

list_move(&pivot->list, &list_less);

並且把後面的 HHHH (&pivot->list, &list_less); 刪除。

簡化迴圈內的 if

if 內的條件式中，因為 stack 內每一個 list 都一定有一個以上的元素。故可簡化：

if (!list_empty(&partition) && !list_is_singular(&partition)) {

可改為

if (!list_is_singular(&partition)) {

簡化當 `partition` 只有一個元素時的情況

另外在 else 裡面，又多了一層迴圈。但實際上也是不斷的從 stack 中取出 list 放到 head 裡。故 else body 直接用 list_move_tail 把從 stack 取出來的 list 中唯一的元素放到 head 內即可。整個 else body 可改為

list_move_tail(partition.next, head);

減少程式深度

經過上面的簡化， else 內只剩下一個 statement ，故改用 early continue 的方式，把原本 if body 拿到外面，而 if statement 改為

if (list_is_singular(&partition)) {
    list_move_tail(partition.next, head);
    continue;
}

因為這部份的改寫比較複雜，建議直接看下一節的程式碼。

程式改寫優化

跟據上面的優化，可以更加優雅

#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 函式。

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;
        }
    }
}

目前這個版本的程式在已經排序好的 linked list ，可能到

O (n^{2})

的 worst case 。
改進的方法：除了成本比較大的 median of medians 外，我比較傾向用隨機挑選 pivot 的方式。
除此之外，再加入 fat pivot ，來改善全部節點都是相等的情況。另外隨機選 pivot 希望還是能保持穩定排序的特性。

TODO 實作此改進

Hybrid Sort 混合排序

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 比較函式的，並透過傳入的比較函式進行數值比較。

實驗所用程式碼

測驗3

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 節點）

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 二次會被抵消掉。

我覺得 cmp 用指標不是很好。二個記憶體位址進行 xor 後的結果就已經不是指向一個有效的記憶體位址，不該再用指標來存。我覺得可以多定義一個型別 typedef uintptr_t xorlist_cmp_t; 來區分比較好。

巨集和相關函式

XOR_COMP 巨集，會把 a 和 b 二個 xor_node_t 指標記憶體位址進行 xor 運算再回傳運算結果。但因為在 C 語言內，指標不能進行 xor 運算，故要先轉型為 uintptr_t ，它是一個無號整數，其大小足以儲存指標內的記憶體位址。運算完成後，再轉型回 xor_note_t 。

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

address_of 函式用來取得前一個節點或下一個節點的記憶體位址，基本上就是 xor 運算。n1 和 n2 其中一個放 xor_node_t 中的 cmp 變數，另一個放前一個節點的位址來取得下一節點的位址或放下一個節點的位址來取得前一個節點的位址。

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 本身的指標。

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

例如：

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

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 是指向上一個節點。

#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 一樣，只差在是從串列最後一個節點走訪到第一個節點。故不再多作解釋。

#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 則會在計算下一個節點位址時被使用。

#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 要指向要走訪節點的後一個節點。

#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 用的釋放記憶體函式。

/* 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 。

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 節點。

#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 節點。

這裡其實不用這麼麻煩，因為 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

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;
}

簡化版但又好理解的程式

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 。

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;
}

雖然這個函式裡面變數命名不好，但會這樣子命名，可能是因為它考慮到 n 傳入 target 的下一個節點也可以運作正常的特性來命名。但或許它仍需要有更好的名字。

另外，雖然這個函式是把節點移除，但節點之後可能可以用到其他地方，故我覺得在這裡就要釋放記憶體反而限縮了它的應用。

另一個問題是呼叫 delete_func 沒有檢查記憶體釋放是否成功。這和後面的 xorlist_destroy 函式有進行檢查刪除是否成功形成對比。

~~如果是我，~~ 我會這樣改進：

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 不為空。

assert(delete_func);

接下來宣告和設定此函數內變數的初始值。 real_prev 是目前走訪節點的上一個節點，設定為 head 節點。 node 為目前走訪的節點，設定為第一個節點。 real_prev 為目前走訪節點的下一個節點，設定為 node 的下一個節點。

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 指向第一個節點的下一個節點

real_prev = node;
node = real_next;

以下程式走訪每一個節點，並刪除每一個節點。迴圈內前面四行會先把 real_prev 和 node 都先指向下一個節點，原本的 real_prev 暫存在 tmp 中，最後再把 tmp 刪除。

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 節點時，就不會進入迴圈了。故最後一個節點的空間無法被釋放。

改進如下：

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 。

struct test_node {
    int value;
    xor_node_t xornode;
};

透過 xorlist_delete_prototype 巨集來宣告刪除節點用的函式。

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 均為等一下走訪時的暫存變數。

以下為加入測試資料的程式碼：

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 有點多餘，因為前面已經把每一個節點都刪除，記憶體都釋放了。

2023q1 Homework1 (quiz1)

開發與實驗環境

測驗1

程式的問題

效能改進方式

Hybrid Sort 實作

對 Linux kernel 貢獻 (移植 Timsort)

測驗2

程式問題及可優化之處

Buffer Overflow 問題

善用 LIST_HEAD 巨集

移動 partition 至迴圈內

pivot 直接移到 list_less 內

簡化迴圈內的 if

簡化當 partition 只有一個元素時的情況

減少程式深度

程式改寫優化

不依頼 MAX_DEPTH 解決方案

Hybrid Sort 混合排序

測驗1與測驗2實驗數據

測驗3

資料結構解釋

巨集和相關函式

Read more

2023q1 Homework7 (ktcp)

2023q1 Homework6 (quiz5)

2023q1 Homework5 (assessment)

2023q1 Homework6 (quiz6)

善用 `LIST_HEAD` 巨集

移動 `partition` 至迴圈內

`pivot` 直接移到 `list_less` 內

簡化當 `partition` 只有一個元素時的情況

不依頼 `MAX_DEPTH` 解決方案