# 2024q1 Homework2 (quiz1+2)
contributed by < `yqt2000` >

## [第一週測驗題](https://hackmd.io/@sysprog/linux2024-quiz1#%E6%B8%AC%E9%A9%97-2)

### 測驗一
#### AAAA/BBBB
考慮以下的鏈結串列結構體:

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

挖空的函式操作如下：

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 。

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 值。

    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`。

    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 之間的鍊結。

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

    /* 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)

### 測驗一
### 測驗二
### 測驗三