# 2024q1 Homework2 (quiz1+2)
contributed by < `yqt2000` >
## [第一週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)
### 測驗一
#### AAAA/BBBB
考慮以下的鏈結串列結構體:
```c
typedef struct __node {
struct __node *left, *right;
struct __node *next;
long value;
} node_t;
```
挖空的函式操作如下:
```c
node_t *list_tail(node_t **left)
{
while ((*left) && (*left)->next)
left = &(AAAA);
return *left;
}
int list_length(node_t **left)
{
int n = 0;
while (*left) {
++n;
left = &(BBBB);
}
return n;
}
```
考慮此二者函式輸入 `left` 皆為間接指標(指向實體節點 node_t 的指標的指標),參閱 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E5%BE%9E-Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E8%97%9D%E8%A1%93%E8%AB%87%E8%B5%B7) 裡有詳細的圖文解說 linked list 中間接指標的應用。
將 `(*left)` 作為走訪節點的指標,則更新時應為當前節點指向下個節點的指標的位址`&(*left)->next`
#### CCCC/DDDD/EEEE
以下是運用 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 所實作非遞迴 (non-recursive; iterative) 的快速排序法程式碼: (部分遮蔽)
begin, end 作為指標陣列,儲存要進行排序的節點指標,來模擬stack的行為,避免遞迴函式呼叫 quick_sort。
在從 stack (begin, end)取出 top element 時,採取的行為大致可分為三個步驟:
1. 分隔出 pivot
2. 將 begin[i]+1 ~ end[i] 的 list ,比 pivot 小的接到 left ,比 pivot 大的接到 right
3. 將分類好的節點指標儲存至 stack 。
```c
void quick_sort(node_t **list)
{
int n = list_length(list);
int value;
int i = 0; //index of top of the stack(begin, end)
int max_level = 2 * n;
node_t *begin[max_level], *end[max_level];
node_t *result = NULL, *left = NULL, *right = NULL;
begin[0] = *list;
end[0] = list_tail(list);
while (i >= 0) {
node_t *L = begin[i], *R = end[i];
if (L != R) {
// step 1
node_t *pivot = L;
value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
// step 2
while (p) {
node_t *n = p;
p = CCCC;
list_add(n->value > value ? &right : &left, n);
}
//step 3
begin[i] = left;
end[i] = DDDD;
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = EEEE;
left = right = NULL;
i += 2;
} else {
if (L)
list_add(&result, L);
i--;
}
}
*list = result;
}
```
由此推斷出:p 作為 step 2 走訪的指標,因此CCCC = `p->next`,而DDDD = `list_tail(&left)`; EEEE = `list_tail(&right)`。
而 quicksort 會優先排序 right 部份(於 left, pivot 後推入 stack ),因此當 L==R 時,雖然 list_add 會將 node 插入 beginning of list,但會依序由較大的值開始插入,最後而得排序好的linked list。
### 測驗二
#### AAAA/BBBB/CCCC in func `merge`
顯然在 `merge` 函式中,合併策略採的是逐對合併(one-pair-at-a-time),並且將兩個 list (list_head *a, list_head *b) 合併結果的第一個 node 存於 head指標中。
而 tail 則是間接指標的應用, 因此將 tail 指向 head 指標的記憶體位址處,雖然沒有初始化 head 的值,但仍可藉由間接指標的操作再賦予 head 值。
```c
struct list_head *head;
struct list_head **tail = &head; //AAAA
```
在逐對合併(one-pair-at-a-time)的過程,分別走訪 list a, b 進行合併,而 tail 指標實際上指向的位址是 tail node 的 next 指標的記憶體位置,所以解指標(*tail)可以對 tail node 的 next 進行操作。
當更新完解指標(*tail),須將tail再進行更新,因此須更新為`&(*tail)->next`。
```c
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &(*tail)->next; //BBBB
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &(*tail)->next; //CCCC
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
```
#### DDDD/EEEE in func `build_prev_link`
在 `build_prev_link` 中, head 為空節點, 而至 head->next 到 tail 為非環狀的雙向鍊結串列(non-circular doubly linked list),list 則是須接於 tail 之後的 null-terminated singly-linked list。
因此首先將 list 逐一接至 tail ,再重建 head 與 tail 之間的鍊結。
```c
static void build_prev_link(struct list_head *head,
struct list_head *tail,
struct list_head *list)
{
tail->next = list;
do {
list->prev = tail;
tail = list;
list = list->next;
} while (list);
/* The final links to make a circular doubly-linked list */
tail->next = head; // DDDD = head;
head->prev = tail; // EEEE = tail;
}
```
#### FFFF
```c
/* The final merge; rebuild prev links */
struct list_head *stk0 = tp, *stk1 = stk0->prev;
while (stk1 && stk1->prev)
stk0 = stk0->prev, stk1 = stk1->prev;
if (stk_size <= 1) { // stk_size <= FFFF
build_prev_link(head, head, stk0);
return;
}
merge_final(priv, cmp, head, stk1, stk0);
```
## [第二週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)
### 測驗一
### 測驗二
### 測驗三