owned this note
owned this note
Published
Linked with GitHub
# 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 的目標。
```c
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。
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
故 AAA = `item`,BBB = `list`。
#### CCCC
在初始化完成後,要開始遍歷所有節點,因為是用 item 傳入,所以是遍歷 item ,要用 for_each_entry 。又因會對節點做更動,使用 safe 來確保遍歷不會出現問題。
```c
#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 。
```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;
}
```
比較 i1 和 i2 的值,回傳 i1 - i2 的差。
```c
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`
圖例:
![](https://i.imgur.com/8GSOit7.png)
第一次遞迴後:
![](https://i.imgur.com/Vq4jg3e.png)
#### FFFF
先解釋這段程式碼。
這邊是採用 Divide and Conquer 的作法,對剛剛的 list_less 以及 list_greater 都採用一樣的模式,不斷遞迴一直直到不能再切為止。
```c
list_sort(&list_less);
list_sort(&list_greater);
```
圖例:
我們一樣用剛剛的圖當例子,list_less 以及 list_greater 再經歷數次遞迴後,會變為已經排序好的狀態。
![](https://i.imgur.com/i2oyZOm.png)
再來就是每次遞迴結束後把 less 接到 pivot 左邊, greater 接到右邊。
```c
list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);
```
故 FFF = `list_splice_tail`。
圖例:
得到一個排序好的 list。
![](https://i.imgur.com/UCUOBDt.png)
### 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) 的實作:
```c
#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 的必要。
```c
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\++。
```c
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 ,其作用後續用到後一併解釋。
```c
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
當 top >= 0 意謂 stack 內還有值,則會繼續執行迴圈, 每次迴圈開始時 partition 會先初始化 partition 並把目前 stack 內最上層的 list 接到 partition 後, partition 的意義即為每次迴圈要處理的 list。
```c
while (top >= 0) {
INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);
```
先來看如果 partition 有一個以上的元素會發生什麼事。
跟測驗一類似,也是利用 less greater pivot 三者比較大小來排序。這段程式碼事先初始化 less greater,並把 partition 的第一個值宣告為 pivot。
```c
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 要做的事就是安全遍歷所以節點。
```c
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`。
執行前:
![](https://i.imgur.com/8GSOit7.png)
執行後:
![](https://i.imgur.com/Vq4jg3e.png)
#### HHHHH IIII JJJJ
因為 pivot 比 less 所有值都大,先把 pivot 接到 less 的尾端,也就是 HHHH 在做的事。因為 list_less 及 list_great 尚未排序完成,接下才要做的事情就是把 list_less 及 list_great 放回 stack ,所以 IIII 和 JJJJ 為對應的 stack 位置,放回去的時候要特別注意,大的部份要放在 stack 叫下面,這跟下一段把值從 stack 拿出來完成排序的順序習習相關,詳細見下段解釋。
```c
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 最頂端。
```c
} 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 往下一層。
```c
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執行前:
![](https://i.imgur.com/M3B2Fvl.png)
while執行後:
![](https://i.imgur.com/dJ65tdE.png)
### 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
```c
#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 的位置。
```c
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 的位址。
```c
#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 的位置。
```c
#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)。
```c
#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 巨集。
```c
/* 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。
```c
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 值。
```c
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`
:::