# 2023q1 Homework1 (quiz1)
contributed by < `ItisCaleb` >

## 2023 第一週測驗題

### 測驗 `1`
list Quick Sort (Recursion ver.)

static void list_sort(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    struct item *pivot = list_first_entry(head, struct item, list);
    list_del(&pivot->list);

    struct item *itm = NULL, *is = NULL;
    list_for_each_entry_safe (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            list_move_tail (&itm->list, &list_less);
        else
            list_move_tail (&itm->list, &list_greater);
    }

    list_sort(&list_less);
    list_sort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

程式首先先把 list 的第一個元素作為 `pivot`
把 `pivot`從 list 移走後走訪 list 的每個元素並且比較
若是比 `pivot` 小則連接到 `list_less` 後面
若是比較大則連接到 `list_greater` 後面
並且用 `list_less` 跟 `list_greater` 分別呼叫 `list_sort` 不斷遞迴下去直到只剩下一項
最後由於 `list_less` 跟 `list_greater` 都已經是排序好的狀態
則我們把 `pivot` 重新加入list
並且把 `list_less` 跟 `list_greater` 分別接到 `pivot` 前後就好

### 測驗 `2`

list Quick Sort (Iterative ver.)

先初始化 `stack` 跟 `partition`

struct list_head stack[MAX_DEPTH];
for (int i = 0; i < MAX_DEPTH; i++)
    INIT_LIST_HEAD(&stack[i]);
int top = -1;
list_splice_init(head, &stack[++top]);

struct list_head partition;
INIT_LIST_HEAD(&partition);

然後把 `stack` 最上面的 list 取出來丟進 `partition`

list_splice_init(&stack[top--], &partition);

接著我們便跟一般的 quick sort一樣
選定第一項元素作為 `pivot`
走訪整個 `partition` 並把比較小的元素丟進 `list_less`
比較大的丟進 `list_greater`

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);
}

然後把 `pivot` 接到 `list_less` 後面
最後如果 `list_less` 或是 `list_greater` 不為空就放進 `stack` 裡

list_move_tail (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, &stack[++top]);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, &stack[++top]);

如果我們 `stack` 最上面的 list 只剩下一項
則我們就直接把他取出並接在 head 後面
直到 `stack` 最上面的 list 不只一項為止

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);
}

### 測驗 `3`

#define XOR_COMP(a, b) ((xor_node_t *) ((uintptr_t) (a)) ^ ((uintptr_t) (b)))

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;
    if (node == &list->tail)
        real_next = &list->tail;
    else
        real_next = node;
    real_prev->cmp = n;
    n->cmp = XOR_COMP(real_prev, real_next);
    real_next->cmp = 
        XOR_COMP(n, XOR_COMP(real_prev, real_next->cmp));
    list->count++;

    return 0;
}