2023q1 Homework1 (quiz1)

contributed by < as200188 >

第一題

參考 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

list_sort_nr(struct list_head *head)運作原理

解釋程式碼原理時，不用重複原本的程式碼 (之後隨堂測驗的程式碼規模會達到數百行)，只要列出關鍵程式碼。

jserv

一開始先判斷傳進來的指標是否為空或只有一個節點，若是則不需處理，直接 return。
宣告一個大小為 512 個節點的 stack，並做初始化，每個節點的 prev 和 next 都指向自己。
list_splice_init(head, &stack[++top]);
讓 stack[0] 裡面放的 head 指向 head 所指向的 list，然後初始化 head(即第一個 argument)

注意作業書寫規範，中英文間用一個半形空白字元區隔。

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

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計算壓縮位址。