# 2023q1 Homework (quiz1)
contributed by < [cin-cout](https://github.com/cin-cout) >
[題目](https://hackmd.io/@sysprog/linux2023-quiz1)

## 測驗一
### 延伸問題:

1. 解釋上述程式碼運作原理
2. 針對 Quick sort 提出上述程式碼的改進方案並實作
3. 引入上述的 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
4. BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻
## Question
以下程式碼實作快速排序法，數值由小到大排列，並確保可達到 stable sorting 的目標。

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

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

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

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

#### AAAA BBBB
AAA 與 BBB 可以一起回答，list_first_entry 是在找 container ，並將其位置回傳給 pivot 儲存，從 linux source code 可以得知 AAA 為 type ， BBB 為 member。

#define list_entry(node, type, member) container_of(node, type, member)

故 AAA = `item`，BBB = `list`。

#### CCCC
在初始化完成後，要開始遍歷所有節點，因為是用 item 傳入，所以是遍歷 item ，要用 for_each_entry 。又因會對節點做更動，使用 safe 來確保遍歷不會出現問題。

#define list_for_each_entry_safe(entry, safe, head, member)                \
    for (entry = list_entry((head)->next, __typeof__(*entry), member),     \
        safe = list_entry(entry->member.next, __typeof__(*entry), member); \
         &entry->member != (head); entry = safe,                           \
        safe = list_entry(safe->member.next, __typeof__(*entry), member))

CCC = `list_for_each_entry_safe`

#### DDDD EEEE
先看 cmpint 的 code 。

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

比較 i1 和 i2 的值，回傳 i1 - i2 的差。

if (cmpint(&itm->i, &pivot->i) < 0)
            DDD (&itm->list, &list_less);
        else
            EEE (&itm->list, &list_greater);

題目比較 itm 與 pivot（first entry） 的值，小於 0 代表 itm 比較小。
比較小的會放到 list_less 的頭。
比較大的會放到 list_great 的頭。
而 list_move 可以做到這件事。
故 DDD = EEE = `list_move`

圖例：

第一次遞迴後：

#### FFFF
先解釋這段程式碼。
這邊是採用 Divide and Conquer 的作法，對剛剛的 list_less 以及 list_greater 都採用一樣的模式，不斷遞迴一直直到不能再切為止。

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

圖例：
我們一樣用剛剛的圖當例子，list_less 以及 list_greater 再經歷數次遞迴後，會變為已經排序好的狀態。
再來就是每次遞迴結束後把 less 接到 pivot 左邊， greater 接到右邊。

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

故 FFF = `list_splice_tail`。
圖例：
得到一個排序好的 list。

### Answer
:::success
AAA = `item`
BBB = `list`
CCC = `list_for_each_entry_safe`
DDD = EEE = `list_move`
FFF = `list_splice_tail`
:::

## 測驗 2
### 延伸問題:

1. 解釋上方程式碼運作原理，指出設計和實作的缺失
2. 比較測驗 1 和測驗 2 的程式碼，設計實驗來分析二者效能，解釋為何非遞迴的實作未能總是比遞迴的實作快
3. 提出效能改進方案，特別是避免依賴 MAX_DEPTH
4. 引入 Introsort，也就是 quick sort 和 heap sort (或其他可避免前者 O(n2)最差時間複雜度的演算法)。加入 heapsort 的原因為，當 quicksort 迭代 2∗log(n) 次後還排序完成，那就很可能會得到 O(n2) 時間複雜度。此時切換為 heap sort 能將其時間複雜度控制在 O(nlogn
### Question
延續上方測驗 1，參考 Optimized QuickSort — C Implementation (Non-Recursive)，將以下程式碼改寫為非遞迴 (non-recursive; iterative) 的實作:

#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 = -1;
    list_splice_init(head, &stack[++top]);

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);
        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);
            struct item *pivot =
                list_first_entry(&partition, struct item, list);
            list_del(&pivot->list);
            INIT_LIST_HEAD(&pivot->list);

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

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
        } else {
            top++;
            list_splice_tail(&partition, &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);
            }
        }
    }
}

一開始是防範機制，若 list 為空或是只有一個元素則沒有 sort 的必要。

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

沒遞迴是利用 list 和 top 實做 stack 的功能，完成後續 sort。
這段程式主要是 stack 的初始化，把 stack 內每一個位置的 list head 都初始化， top 為紀錄 stack 最上層的指針，初始值因為沒有存任何東西，所以放入-1，最後則是把尚未排序的 list 放入 stack[0] 層，這邊要住意一定要 ++top 不能寫 top\++。

    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]);

初始化 partition ，其作用後續用到後一併解釋。

    struct list_head partition;
    INIT_LIST_HEAD(&partition);

當 top >= 0 意謂 stack 內還有值，則會繼續執行迴圈， 每次迴圈開始時 partition 會先初始化 partition 並把目前 stack 內最上層的 list 接到 partition 後， partition 的意義即為每次迴圈要處理的 list。

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);

先來看如果 partition 有一個以上的元素會發生什麼事。
跟測驗一類似，也是利用 less greater pivot 三者比較大小來排序。這段程式碼事先初始化 less greater，並把 partition 的第一個值宣告為 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);
            struct item *pivot =
                list_first_entry(&partition, struct item, list);

#### GGGG
接下來這段跟測驗一模一樣，題目比較 itm 與 pivot（first entry） 的值，小於 0 代表 itm 比較小。
比較小的會放到 list_less 的頭。
比較大的會放到 list_great 的頭。
GGGG 要做的事就是安全遍歷所以節點。

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

故 GGGG = `list_for_each_entry_safe`。

執行前：

執行後：

#### HHHHH IIII JJJJ
因為 pivot 比 less 所有值都大，先把 pivot 接到 less 的尾端，也就是 HHHH 在做的事。因為 list_less 及 list_great 尚未排序完成，接下才要做的事情就是把 list_less 及 list_great 放回 stack ，所以 IIII 和 JJJJ 為對應的 stack 位置，放回去的時候要特別注意，大的部份要放在 stack 叫下面，這跟下一段把值從 stack 拿出來完成排序的順序習習相關，詳細見下段解釋。

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);

故 HHHH = `list_move_tail` 。
IIII = JJJJ = `&stack[++top]`。

接下來講解若 while 迴圈內，partition 只有一個元素的處理。就是直接把 partition 的元素放到 stack 最頂端。

        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);

#### KKKK
partition 只有一個元素的處理，會 stack 內由上到下一個元素的 list 接到 head 後端，直到 stack[top] 的元素不為一個，剛剛上段有解釋了。在把 list 放入 stack 時由下到上，分別會是由大到小，所以在由上到下將 list 拿出時，會是由小到大，符合我們要 ascending sort 。特別要注意的是 KKKK ，雖然他的作用為把已經清空的 stack 做初始化，但為了配合 while 要由上到下去檢查 stack ，所以還要加入 top-- 的指令，讓 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);
            }

故 KKKK = `&stack[top--]`。

while執行前：

while執行後：

### Answer
:::success
GGGG = `list_for_each_entry_safe`
HHHH = `list_move_tail`
IIII = JJJJ = `&stack[++top]`
KKKK = `&stack[top--]`
:::

## 測驗 3
### 延伸問題:

1. 解釋上述程式碼運作原理，指出其實作缺陷並改進
2. 在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
3. 修改 xorlist_destroy，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放

### Question

#include <assert.h>
#include <errno.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

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;

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

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

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

#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)

#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)

#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)

#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)

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

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)

#define XORLIST_INIT(h)           \
    do {                          \
        (h).head.cmp = &(h).tail; \
        (h).tail.cmp = &(h).head; \
        (h).count = 0;            \
    } while (0)

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 = MMMM;
    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, PPPP));
    list->count++;

    return 0;
}

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

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 *real_next = address_of(real_prev, node->cmp);
    xor_node_t *tmp = real_prev;
    real_prev = node;
    node = real_next;

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

    return 0;
}

struct test_node {
    int value;
    xor_node_t xornode;
};

xorlist_delete_prototype(test_delete, _node)
{
    struct test_node *node = container_of(_node, struct test_node, xornode);
    free(node);
    return 0;
}

int main(void)
{
    xor_list_t list;
    xor_node_t *p1, *p2;

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

    xor_node_t *real_prev, *real_next, *node;
    int i = 0;
    printf("xorlist_for_each test\n");
    xorlist_for_each(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_from test\n");
    xorlist_for_each_from(node, p1, p2, real_prev, real_next, &list)
    {
        printf("node %d\n",
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_each_from_prev test\n");
    xorlist_for_each_from_prev(node, p1, p2, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    i = 0;
    printf("xorlist_for_each_prev test\n");
    xorlist_for_each_prev(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    printf("xorlist_del test\n");
    xorlist_del(&list, p2, p1, xorlist_delete_call(test_delete));
    i = 0;
    xorlist_for_each(node, real_prev, real_next, &list)
    {
        printf("node [%d] %d\n", i++,
               container_of(node, struct test_node, xornode)->value);
    }

    xorlist_destroy(&list, xorlist_delete_call(test_delete));

    return 0;
}

以下有參考 [yanjiew1](https://hackmd.io/ZoG1Z852SQqrk4jFHc9czQ?view#2023q1-Homework1-quiz1)，這位同學分析得很透徹。
在資料結構方面， xor linked list 使用了 xor_list_t 作為 node 的結構體和 xor_node_t 作為 list 的結構體。

xor_node_t 方面裡面只存了 cmp 一個變數，意義為該 node 前後 node 的 xor 值。
xor_list_t 內存了 head 和 tail 分別代表此 list 的最頭和最尾 node 的位置，其意義在初始化函式可以更加明白， count 則是除儲存此 list 的 node 數量。

至於為什麼 cmp 要儲存前後 node 的 xor 值，這則是利用 xor 的特性： `A ^ B ^ B = A `，即由 xor 組成的運算式，同樣的數值 xor 二次會被抵消掉，所以只要有前一個 node 的位置加上 cmp 就可以找到下一個 node 的位置，反之亦然，有下一個 node 的位置加上 cmp 就可以找到前一個 node 的位置。

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;

#### LLLL
依照上述邏輯，計算 cmp 需要對前後 node 做 xor ，但 c 內 ptr 是不能做 xor 運算的，所以要先轉換成 uintptr_t 的形式。
address_of 則是在尋找前一個 node 或是下一個 node 的位置，傳入值為：
1. 前一個 node 的位置和現在 node 的 cmp -> 找下一個 node 的位址。
2. 下一個 node 的位置和現在 node 的 cmp -> 找上一個 node 的位址。

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

static inline xor_node_t *address_of(xor_node_t *n1, xor_node_t *n2)
{
    assert(n1 && n2);
    return XOR_COMP(n1, n2);
}

故 LLLL = `(uintptr_t) (a) ^ (uintptr) (b)`。

這邊和原本 list.h 的 container_of 一樣，是給定 member 位置 ptr ，尋找在包含該 member 的 type 的位置。

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

這段一起解釋。
xorlist_for_each：從頭遍歷所有 node 。
xorlist_for_each_prev：從尾遍歷所有 node 。
xorlist_for_each_from：從 pos2 往後遍歷所有 node 。
xorlist_for_each_from_prev：從 pos2 往前遍歷所有 node 。

以 xorlist_for_each 來解釋，邏輯跟意開始說的一樣:

:::success
為什麼 cmp 要儲存前後 node 的 xor 值，這則是利用 xor 的特性： `A ^ B ^ B = A `，即由 xor 組成的運算式，同樣的數值 xor 二次會被抵消掉，所以只要有前一個 node 的位置加上 cmp 就可以找到下一個 node 的位置，反之亦然，有下一個 node 的位置加上 cmp 就可以找到前一個 node 的位置。
:::
1. 一開始初始值給 rp list 的頭，node 則為 head.cmp 即為 head 後第一個 node。
2. 更新時給 address_of(rp, node->cmp) 代表的是前一點（rp）和現在 node 的 cmp (node->cmp) 的 xor 值，即為下一個 node 的位址，rp = node 和 node = rn 則是把 rp 換成現在的 node ，node 換成下一個 node。
4. 停止條件為 node ＝ tail 意即下一個 node 就是 tail 了不需要再遍歷了。

而 xorlist_for_each_from 的差別在於，因為不是從頭遍歷，不是從 head 開始。需要額外傳入前一個 node 的位址（pos1）以及要作為開頭遍歷的點的位置（pos2）。

#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)

#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)

#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)

#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)

delete 巨集。

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

此段為初始化 node 分為函式版本以及巨集版本，意思一樣，就是將 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)

#### MMMM
跟 list.h 內的 add 功能相同，在 head 與第一個 node 之間插入一個 node。
傳入值為 list 和想要插入的 node。

因為要對插入的 node.cmp 做更新，必須知道其前一個 node （real_prev）和下一個 node (real_next)的位址。因為是插入頭和第一個 node 之間，所以 prev 一定是 ＆list->head。

參考 [yanjiew1](https://hackmd.io/ZoG1Z852SQqrk4jFHc9czQ?view#2023q1-Homework1-quiz1)其實多一個條件判斷 head 後面是不是 tail 沒有意義，因為 head.cmp 已經紀錄了 head 下一個 node 的位址無論他是不是 tail。但測驗中還是把它分出來判斷，所以當今天原本 head 下一個為 tail 時， real_next 可以直接放 &list->tail。

接下來就是分別更新 real_prev ，插入 node 以及 real_next 的 cmp。
1. head 的 cmp 會直接指向其下一個 node ，所以直接放插入 node 之位址（n）。
2. 插入 node 的位址為其前後 node 位址的 xor 值，故為 XOR_COMP(real_prev, real_next) 。
3. real_next->cmp 為其前後 node 的 xor 值，前面的 node 即為 n ，而後面一個 node 則是 real_next 原本前一個 node 的位址（real_prev）和 real_next 原本的 cmp (real_next->cmp) 的 xor 值。

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 = MMMM;
    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, PPPP));
    list->count++;

    return 0;
}

故 MMMM = `&list->tail` 。
故 PPPP = `real_next->cmp`

:::info
**TODO** 將剩下的程式碼解釋完。
:::

### Answer
:::success
LLLL = `(uintptr_t) (a) ^ (uintptr) (b)`
MMMM = `&list->tail`
PPPP = `real_next->cmp`
:::