owned this note
owned this note
Published
Linked with GitHub
---
tags: linux2023
---
# 2023q1 Homework1 (quiz1)
contributed by < `as200188` >
## 第一題
參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)
### static void list_sort(struct list_head *head)運作原理
若 head 為空或只有一個節點，則不需處理，直接 return。
宣告 list_less 和 list_greater 用來指向小於 pivot 的多個節點和大於 pivot 的多個節點。
取 list 第一個節點作為 pivot。然後將該 pivot 從 list 中移除。
```
list_for_each_entry_safe(itm, is, head, list) {
if (cmpint(&itm->i, &pivot->i) < 0)
list_move(&itm->list, &list_less);
else
list_move(&itm->list, &list_greater);
}
```
逐一走訪 list 並將小於 pivot 值的節點先從原 list 上移除，再將節點移到 list_less 的第一個節點，大於等於 pivot 值的，先從原 list 上移除，再將節點移到 list_greater 的第一個節點。
```
list_sort(&list_less);
list_sort(&list_greater);
```
遞迴處理小於 pivot 的 list 和 大於等於 pivot 的 list。
```
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
```
將 pivot 加到 list 的第一個節點。
此時的 list_less 和 lis_greater 是已排序好的，將 list_less 串接到 list 的頭，list_greater 串接到 list 的尾巴，即可得到已排序的 list。
## 第二題
參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h)
### list_sort_nr(struct list_head *head)運作原理
:::warning
解釋程式碼原理時，不用重複原本的程式碼 (之後隨堂測驗的程式碼規模會達到數百行)，只要列出關鍵程式碼。
:notes: jserv
:::
一開始先判斷傳進來的指標是否為空或只有一個節點，若是則不需處理，直接 return。
宣告一個大小為 512 個節點的 stack，並做初始化，每個節點的 prev 和 next 都指向自己。
```list_splice_init(head, &stack[++top]);```
讓 stack[0] 裡面放的 head 指向 head 所指向的 list，然後初始化 head(即第一個 argument)
:::danger
注意作業書寫規範，中英文間用一個半形空白字元區隔。
:notes: jserv
:::
假設要處理的 list 為 2->1->3。
```
struct list_head partition;
INIT_LIST_HEAD(&partition);
```
宣告 partition 節點並初始化。
此處可優化成 ```LIST_HEAD(partition)```
top 現在為 0 開始進入迴圈，先將 partition 做初始化。
```list_splice_init(&stack[top--], &partition);```
讓 partition 指向 stack[0] 裡面放的 head 所指向的 list，然後初始化 stack[0] 裡面放的 head，最後 top - 1， 現在 top 為 -1。
``` if (!list_empty(&partition) && !list_is_singular(&partition)) ```
若 partition 指向的 list 為非空且非只有一個節點，則條件成立。
```struct list_head list_less, list_greater;```
宣告兩個節點變數，list_less 用來指向比 pivot 小的 list，list_greater 用來指向比 pivot 大的 list。
宣告後都先做初始化。
```struct item *pivot = list_first_entry(&partition, struct item, list);```
list_first_entry(head, type, member)
現在 partition 是指向 list 的第一個節點，所以作為第一個 argument，而 list 由多個 item 節點串接而成，須利用 container_of 來計算 item 節點的位址，所以要傳入母結構和成員，作為第二個和第三個 argument，最後得到 list 上的第一個節點，並回傳該節點的位址。
```list_del(&pivot->list);```
將 pivot 節點從 list 中移除。
現在 partition 為指向舊 list 的第二個節點, 即指向新 list 的第一個節點。
```INIT_LIST_HEAD(&pivot->list);```
初始化 pivot 節點的 list 成員。
```
struct item *itm = NULL, *is = NULL;
list_for_each_entry_safe(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_for_each_entry_safe（itm, is, &partition, list）```
itm 為 list 的 iterator，用來逐一走訪 list，is 為用來存放下一個節點的資訊。逐一走訪時，只能刪除 iterator 指向的節點。
比較 pivot 節點上的值 和 iterator 指向的節點上的值，若 iterator 指向的節點的值比 pivot 小，則將該節點從原 list 上移除，並加到 list_less 的頭，若值比較大，則加到 list_greater 的頭。
此段程式碼有可優化的地方，從 list_move 的實做可發現，該實做會先做 list_del 將節點從 list 上移除，再將該節點加到指定的 list 的頭。也就是說，在比較值的上一行：```list_del(&itm->list);```是可以移除的。
```list_move_tail(&pivot->list, &list_less);```
將 pivot 加到 list_less 的尾巴。
當前 top 為 -1，stack[0] 已經過初始化(已在 list_splice_init 時初始化了)。
```
if (!list_empty(&list_greater))
list_splice_tail(&list_greater, &stack[++top]);
```
若值較大的 list 非空，則將該 list_greater 串接到 stack[0] 的尾巴。
```
if (!list_empty(&list_less))
list_splice_tail(&list_less, &stack[++top]);
```
若值較小的 list 非空，則將該 list_less 串接到 stack[1] 的尾巴。
回到 while 判斷式，現在 top 為 1，符合條件，進入迴圈。
初始化 partition 後，將 stack[1] 串接到 partition 的頭(即 partition 指向 stack[1] 所指向的地方，該指向的地方為 list 的第一個 item)，最後 top - 1，現在 top 為 0，stack[0]為 list_greater，stack[1]為 list_less，partition 為 list_less。
現在
top: 0
stack[0] list_greater: 3
stack[1] list_less: 1->2
若 partition 為非空且非單一節點，則進入 if 讓 partition 指向的 list_less 上的節點與 pivot 做比較，然後分割，並放入 stack。
pivot 為 1，最後將 pivot 加到 list_less 的尾巴。
現在
top: 2
stack[0] list_greater: 3
stack[1] list_greater: 2
stack[2] list_less: 1
回到 while 判斷式，現在 top 為 2，符合條件，進入迴圈。
初始化 partition 後，將 stack[2] 串接到 partition 的頭，然後 top - 1。
現在 top 為 1。
因 partition 指向的 list 只有一個節點，不會進入 if 。
進入else。
```
top++;
```
top + 1 後為 2。
現在
top: 2
stack[0]: list_greater: 3
stack[1]: list_greater: 2
stack[2]: 已初始化
partition: list_less: 1
```
list_splice_tail(&partition, &stack[top]);
```
將 partition 加到 stack[2] 的尾巴。
現在
top: 2
stack[0]: list_greater: 3
stack[1]: list_greater: 2
stack[2]: list_less: 1
partition: list_less: 1
```
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(&stack[top--]);
list_add_tail(&tmp->list, head);
}
```
當 top >= 0 且 stack[top] 裡面只有一個節點時，將該節點加到 head 的尾巴。並初始化stack[top] 然後將 top - 1。
這段程式可優化成:
```
while (top >= 0 && list_is_singular(&stack[top])) {
struct item *tmp = list_first_entry(&stack[top], struct item, list);
INIT_LIST_HEAD(&stack[top--]);
list_move_tail(&tmp->list, head);
}
```
結論: 當 stack[top] 只有一個節點時，會是當前 list 裡面的最小值，stack[top] 下面都會是 list_greater，所以每次當頂端只有一個節點時，就將節點加到 head 的尾巴，最後就可得到已排序的 list。如果在處理 stack[top] 中途遇到非單一節點時，就回到 if 將其 list 拆開放入 stack，目標是讓 stack[top] 為單一節點和當前最小值。
## 第三題
參考 [XOR linked list](https://en.wikipedia.org/wiki/XOR_linked_list)
### int xorlist_add(xor_list_t *list, xor_node_t *n) 運作原理
```
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;
}
```
list 經過初始化後，
list :
head: {cmp: 指向 list 的 tail}
tail: {cmp: 指向 list 的 head}
count: 0
建立一個 xor_list，每次將初始化後的節點加到 list 的第一個節點，做 1000 次。
```
int xorlist_add(xor_list_t *list, xor_node_t *n)
```
首先是第一次插入節點。
```
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
```
real_prev: 指向 list 的 head。
node: 指向 head 的 cmp 所指向的地方，即指向 list 的 tail。
```
if (node == &list->tail)
real_next = &list->tail;
else
real_next = node;
```
條件成立，real_next 為指向 list->tail。
```
real_prev->cmp = n;
```
real_prev 現在是指向 list 的 head，也就是 list 的 head 的 cmp 指向 n 所指向的地方，該段程式會將 n 指向的節點加到 list 的最前端。
令 A 是 address of list head
令 B 是 address of list tail
令 C 是 第一個節點的位址
現在
list :
head: {cmp: C}
tail: {cmp: A}
real_prev: 指向 list 的 head
real_next: 指向 list 的 tail
```
n->cmp = XOR_COMP(real_prev, real_next);
```
計算 n 指向的節點的壓縮位址(cmp)，將該節點前面節點的 address 和後面節點的 address 做 XOR。
該節點的壓縮位址為 $(A \oplus B)$
```
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
```
計算 list tail 的壓縮位址: $C\oplus(A \oplus A)=C$
現在
list:
head: {cmp: C}
tail: {cmp: C}
第一個節點位址: C
cmp: $(A \oplus B)$
驗算:
list 目前只有一個節點
前一個節點位址(head 的位址):A
第一個節點的壓縮位址:$(A \oplus B)$
計算下一個節點的位址:
$A\oplus(A \oplus B)=B$ 得到 B 便可前往尾巴，會走到 tail。
下一步:
尾巴前面的位址: C
尾巴的壓縮位址: C
計算下一個位址: $(C \oplus C)=0$
得到 0 便可知道已走到尾巴。
可以發現該 list 雖然只有一個存放資料的節點，但該節點的壓縮位址需要 head 和 tail 的位址做 XOR 計算，而且需要走到 tail 才能計算出下一個位址是 0
再度進入迴圈，加入新節點
現在
list:
head: {cmp: C}
tail: {cmp: C}
第一個節點位址: C
cmp: $(A \oplus B)$
```
xor_node_t *real_prev = &list->head;
xor_node_t *node = real_prev->cmp;
```
執行完後
real_prev: A
node: C
```
if (node == &list->tail)
real_next = n;
else
real_next = node;
```
條件不成立，real_next 為第一個節點(address: C)
```
real_prev->cmp = n;
```
假設新節點的位址為 D
將新的節點加到 list 的最前端
現在
list:
head: {cmp: D}
tail: {cmp: C}
第一個節點位址: D
cmp: NULL
第二個節點位址: C
cmp: $(A \oplus B)$
real_prev: A
real_next: C
```
n->cmp = XOR_COMP(real_prev, real_next);
```
計算 n 的壓縮位址為$(A \oplus C)$
因為新節點是加到 list 的第一個節點(head 後面)，所以前面是 head 後面是原本的第二個節點(address:C)，壓縮位址為前後位址做 XOR 計算。
現在
list:
head: {cmp: D}
tail: {cmp: C}
第一個節點位址: D
cmp: $(A \oplus C)$
第二個節點位址: C
cmp: $(A \oplus B)$
```
real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
```
更新第二個節點的壓縮位址，因為第二個節點的前面原本是 head，現在因為加了新節點，前面變成新節點，所以需要重新計算壓縮位址。
將前面的位址和當前自己的壓縮位址和原本前面的位址做 XOR 計算，這樣可以消掉原本前面的位址，保留後面的位址的資訊，得到 $(D \oplus (A \oplus (A \oplus B)))=(D \oplus B)$
現在
list:
head: {cmp: D}
tail: {cmp: C}
第一個節點位址: D
cmp: $(A \oplus C)$
第二個節點位址: C
cmp: $(D \oplus B)$
驗算:
第二個節點前面是 D
第二個節點壓縮位址: $(D \oplus B)$
計算下一個位址: $D\oplus (D \oplus B)=B$
得到 B 便可走到 tail
tail 前面是 C
tail 壓縮位址為 C
計算下一個位址: $C\oplus C = 0$
算出 0 可得知已走到最後。
結論:
該程式運作需要 head 和 tail 的位址來計算插入的第一個節點的壓縮位址，後面插入新節點到最前端，計算壓縮位址需要 head 的位址和後面一個節點的壓縮位址。
```
#define XOR_COMP(a, b) ((xor_node_t *) ((uint64_t)a^(uint64_t)b))
```
假設 64 bits 機器。
用XOR計算壓縮位址。
Google Drive
Gist
Clipboard
Sign in with Wallet
