2020q1 Homework3 (quiz3)

contributed by < ZhuMon >

tags: `linux2020`

2020q1 的意思是 2020 年的第 1 季，顯然我們的開學日就在這範圍

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

原來如此，之後會注意

第 3 週測驗題

測驗 `1`

本文皆以 addr(a) 代表 a 的位址， link(a) 代表 a->addr

題目

補完以下程式碼

#include <stdint.h>

typedef struct __list list;
struct __list {
    int data;
    struct __list *addr;
};

#define XOR(a, b) ((list *) ((uintptr_t) (a) ^ (uintptr_t) (b)))

void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}

void delete_list(list *l) {
    while (l) {
        list *next = l->addr;
        if (next)
            next->addr = XOR(next->addr, l);
        free(l);
        l = next;
    }
}

list *sort(list *start)
{
    if (!start || !start->addr)
        return start;

    list *left = start, *right = start->addr;
    left->addr = NULL;
    right->addr = XOR(right->addr, left);

    left = sort(left);
    right = sort(right);

    for (list *merge = NULL; left || right;) {
        if (!right || (left && left->data < right->data)) {
            list *next = left->addr;
            if (next)
                next->addr = XOR(left, next->addr);

            if (!merge) {
                start = merge = left;
                merge->addr = NULL;
            } else {
                merge->addr = LL1;
                left->addr = LL2;
                merge = left;
            }
            left = next;
        } else {
            list *next = right->addr;
            if (next)
                next->addr = XOR(right, next->addr);

            if (!merge) {
                start = merge = right;
                merge->addr = NULL;
            } else {
                merge->addr = RR1;
                right->addr = RR2;
                merge = right;
            }
            right = next;
        }
    }

    return start;
}

解析 XOR linked list 運作機制

HackMD 內文的縮排 (indention) 深度不要太深，不然難以編輯和檢測語法問題

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

好的，會再思考一下架構

`insert_node`












void insert_node(list **l, int d) {
    list *tmp = malloc(sizeof(list));
    tmp->data = d;

    if (!(*l)) {
        tmp->addr = NULL;
    } else {
        (*l)->addr = XOR(tmp, (*l)->addr);
        tmp->addr = *l;
    }
    *l = tmp;
}

從 function 名稱可以猜出這個 function 可能是要在 linked list 插入一個 node
這個 function 傳入的參數有兩個，一個是 list **l，一個是 int d
- *l 指向的 node 有三種可能
  1. linked list 最前面的 node
  2. linked list 中間的 node (除了最前面以及最後面的任何 node)
  3. linked list 最後面的 node
  1. 粗略地往下掃過，在 insert_node() 中，沒有看到將 *l 移動很多步的程式碼（ e.g. while、for），所以可以判定新的 node 會在 *l 的旁邊
  2. 由於 XOR linked list 為變相的 doubly linked list，所以第 1 項與第 3 項是相同的
- d 可以從第 13 行 tmp->data = d 得知是新 node 的 data
接下來思考 if-else 的功用
- 進入第 16 行的條件是 *l 為 NULL，也就是傳入的 linked list 為空，於是將新增的 node： tmp 的 addr 設為 NULL
- 若是 linked list 不為空，則進入第 18 行
- 從 XOR linked list 可以知道，每次新增一個 node 必須將 addr 指定為前後兩個 node address 的 XOR
以數學描述如下

$l i n k (a) = 0 \oplus a d d r (b)$ = addr(b)

$l i n k (b) = a d d r (a) \oplus a d d r (c)$

$l i n k (c) = a d d r (b)$
- case 1 : *l 指向 a (linked list 的第一個 node)
  - 預期結果：
    - 插入新的 node 到 linked list 的前端
      
      $l i n k (t m p) = a d d r (a)$
      
      $l i n k (a) = a d d r (t m p) \oplus a d d r (b)$
      
      $l i n k (b) = a d d r (a) \oplus a d d r (c)$
      
      $l i n k (c) = a d d r (b)$
    - *l 最後會指向 tmp
  - 實際結果：
```
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
```
    - initial
      
      $l i n k (* l) = l i n k (a) = 0 \oplus a d d r (b)$ = addr(b)
    - line 18
      
      $\begin{aligned} l i n k^{'} (* l) & = a d d r (t m p) \oplus l i n k (* l) \\ = a d d r (t m p) \oplus 0 \oplus a d d r (b) \\ = a d d r (t m p) \oplus a d d r (b) \end{aligned}$
    - line 19
      
      $l i n k (t m p) = a d d r (* l) = a d d r (a)$
    - *l = tmp;
    - 符合設想
- case 2 : *l 指向 b (linked list 的中間 node)
  - 預期結果：
    - 插入新的 node 到 linked list 的中間（b 的前面或後面）
      
      $l i n k (a) = a d d r (b)$
      
      $l i n k (b) = a d d r (a) \oplus a d d r (t m p)$
      
      $l i n k (t m p) = a d d r (b) \oplus a d d r (c)$
      
      $l i n k (c) = a d d r (t m p)$
      
      or
      
      $l i n k (a) = a d d r (t m p)$
      
      $l i n k (t m p) = a d d r (a) \oplus a d d r (t m p)$
      
      $l i n k (b) = a d d r (t m p) \oplus a d d r (c)$
      
      $l i n k (c) = a d d r (b)$
    - *l 指向 b 或 tmp
  - 實際結果：
```
(*l)->addr = XOR(tmp, (*l)->addr);
tmp->addr = *l;
```
    - initial
      
      $l i n k (* l) = l i n k (b) = a d d r (a) \oplus a d d r (c)$
    - line 18
      
      $\begin{aligned} l i n k^{'} (* l) & = a d d r (t m p) \oplus l i n k (* l) \\ = a d d r (t m p) \oplus a d d r (a) \oplus a d d r (c) \end{aligned}$
    - line 19
      
      $l i n k (t m p) = a d d r (* l) = a d d r (b)$
    - 與設想不同
- case 3
  - 可視為 case 1 的 reverse
結論
- insert_node 會在 linked list 插入一個 node，視傳入的 *l 位置為何
- 若是傳入的 *l 為第一個，則在前面插入；若是最後一個，則在最後插入
- 最後會將 *l 指向新 node

`delete_list`









void delete_list(list *l) {
    while (l) {
        list *next = l->addr;
        if (next)
            next->addr = XOR(next->addr, l);
        free(l);
        l = next;
    }
}

從字面上可以猜到這個 function 用來將整個 linked list 刪除
若傳入的 linked list : l 存在，才進入 while
要在 XOR linked list 中移動，必須使用以下特性
- $A \oplus 0 = A$
- $A \oplus A = 0$
- 將自己存放的 data 與前一個 node 的 address 作 XOR，可以得到下一個 node
進入 while 前的狀態
以 addr(a) 代表 a 的位址， link(a) 代表 a->addr

$l i n k (a) = a d d r (b)$

$l i n k (b) = a d d r (a) \oplus a d d r (c)$

$l i n k (c) = a d d r (b)$

進入 while 後，會由一個指標 next 存放

l i n k (l)





list *next = l->addr;
if (next)
    next->addr = XOR(next->addr, l);
free(l);
l = next;

$n e x t = l i n k (l)$
若 l 指向 a

$l i n k (l) = l i n k (a)$

$n e x t = l i n k (a) = a d d r (b)$

next 存在，進入 line 28

$\begin{aligned} l i n k^{'} (n e x t) & = l i n k (n e x t) \oplus a d d r (l) \\ = l i n k (a d d r (b)) \oplus a d d r (a) \\ = l i n k (b) \oplus a d d r (a) \\ = (a d d r (a) \oplus a d d r (c)) \oplus a d d r (a) \\ = (a d d r (a) \oplus a d d r (a)) \oplus a d d r (c) \\ = 0 \oplus a d d r (c) \\ = a d d r (c) \end{aligned}$
可以發現 if 裡，會將 next 指向的 node 的 link 設為下一個 node 的 address
line 29 將 l 指向的 node 釋放

line 30 將 l 指向 next 指向的 node

以此類推，會將整個 linked list 走完，並釋放

XOR Linked List 特性

從前面兩個 function 可以歸納出 XOR Linked List 的幾個特性

第一個 node 和最後一個 node 存放的 link 都是該 node 的前一個 node 的 address
XOR Linked List 是一個雙向 Linked List，且可以藉由同樣步驟從第一個或最後一個走完整個 List
在中間的 node 想要移動，需要有上一個 node 的 address

解題思路

一開始 if 內判斷傳入的 start 是否存在，以及是否超過一個以上的元素

可參照 insert_node()
若 start->addr 為 NULL，則代表 list 內只有一個元素
```
if (!start || !start->addr)
    return start;
```

從變數名稱可以看出接下來可能是要把 Linked list 拆成兩個



list *left = start, *right = start->addr;
left->addr = NULL;
right->addr = XOR(right->addr, left);

用看的可能一時無法知道接下來程式碼的用途，所以試著用數學運算

以下為已知

$l i n k (a) = a d d r (b)$

$l i n k (b) = a d d r (a) \oplus a d d r (c)$

$l i n k (c) = a d d r (b)$
line 39 設定 pointer

$l e f t = a d d r (a), r i g h t = l i n k (a) = a d d r (b)$
因為第一個以及最後一個 node 所存放的 link 都是其旁邊的 node address，所以 right 可以輕易地藉由 start->addr 得到第二個 node address

line 40~41 斷開 Linked list

$l i n k^{'} (l e f t) = a d d r (a) = N U L L$

$\begin{aligned} l i n k^{'} (r i g h t) & = l i n k (r i g h t) \oplus a d d r (l e f t) \\ = l i n k (b) \oplus a d d r (a) \\ = (a d d r (a) \oplus a d d r (c)) \oplus a d d r (a) \\ = a d d r (c) \end{aligned}$

接下來分別將 left、right 丟進 sort，遞迴呼叫，因為左邊都只有一個，所以每次的分開應該會長這樣

進入重頭戲： for

line 48~50 和 line 62~64 可以一起看，又因為 left 經過遞迴呼叫後，都只會剩下一個 node，所以 line 49 的 if 根本不會進入，是以 right 來解說



list *next = left->addr;
if (next)
    next->addr = XOR(left, next->addr);



list *next = right->addr;
if (next)
    next->addr = XOR(right, next->addr);

$n e x t = l i n k (r i g h t)$

$\begin{aligned} l i n k^{'} (n e x t) & = a d d r (r i g h t) \oplus l i n k (n e x t) \\ = a d d r (a) \oplus a d d r (a) \oplus a d d r (c) \\ = a d d r (c) \end{aligned}$

這三行將 next 指向 right 隔壁的 node，若直接取用 right->addr 當作下一個 node 的 address ，right 必定為最前面的 node 或是 link 存放下一個 node 的 address，所以

終於要來解題了，line 52~60 和 line66~74 是對稱的，所以也可以一起看。

這裡第一個 if 限制 merge 為 NULL 時才能進入，掃過整個 for ，並沒有看到將 merge 重設為 NULL，也就是說只有第一次進入才有可能進入第一個 if

只有將 merge 設為 left， left 為 NULL 又不可能進入 line 48









if (!merge) {
    start = merge = left;
    merge->addr = NULL;
} else {
    merge->addr = LL1;
    left->addr = LL2;
    merge = left;
}
left = next;









if (!merge) {
    start = merge = right;
    merge->addr = NULL;
} else {
    merge->addr = RR1;
    right->addr = RR2;
    merge = right;
}
right = next;

假設第一次進入 for 是進入 line 66 的 else。
進入 line 67，將 start 和 merge 都設為 right 所指向的 node，並且斷掉與其他 node 的連結，然後 right 指向 next

假設第二次的 for 是 a->data < c->data，也就是說會進入 line 48，將 Linked list 分開後，應該要合起來，所以應該要想辦法將 left 接到 merge 或 start 後面
- line 56 更動的是 merge->addr，也就是說 LL1 要存放上一個（NULL）的位址以及下一個（left）的位址的 XOR
- 由於要進行推廣，所以上一個 node 的位址不能設為 NULL
- 要得到上一個 node 的位址可以直接拿 merge 的 link，因為正常的 XOR Linked list 最後一個 node 的 link 一定是上一個 node 的 address
- 因此
LL1 = XOR(merge->addr, left)
- line 57 更動的是 left->addr，可以從上圖看到此時 left->addr 為 NULL，由於 left 即將成為最後一個 node，所以必定存放上一個 node 的 address，也就是 merge
LL2 = merge
- line 58 將 merge 向前移動
- 因為對稱，所以 LL3 和 LL4 可以此類推
LL3 = XOR(merge->addr, right)

LL4 = merge

最後將 start 回傳，合併 Linked List，合併的概念如下

也就是一個 Insertion Sort

測驗 `2`

TODO：

第一題延伸問題

第二題

2020q1 Homework3 (quiz3)

tags: linux2020

測驗 1

題目

解析 XOR linked list 運作機制

insert_node

delete_list

XOR Linked List 特性

解題思路

測驗 2

Read more

2020q3 Homework1 (quiz1)

透過 Netfilter 自動過濾廣告

2020q3 Homework3 (dict)

2020q3 Homework2 (quiz2)

tags: `linux2020`

測驗 `1`

`insert_node`

`delete_list`

測驗 `2`