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

# 測驗1

給定 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 作為[〈linked list 和非連續記憶體操作〉](https://hackmd.io/@sysprog/c-linked-list)提及的 Linux 核心風格 circular doubly-linked list 實作，欲處理的節點採用以下結構體:

#include <stdint.h>
#include "list.h"

struct item {                         
    uint16_t i;
    struct list_head list;
};

用以對節點內含值比較的函式:

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

以下程式碼實作快速排序法，數值由小到大排列，並確保可達到 [stable sorting](https://en.wikipedia.org/wiki/Sorting_algorithm) 的目標。

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, AAA, BBB);
    list_del(&pivot->list);

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

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

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

請補完，使其行為符合預期。作答規範:

`AAA` , `BBB` , `CCC` , `DDD` , `EEE` , `FFF` 應以最簡潔的形式撰寫，且符合作業一排版規範 (近似 Linux 核心程式碼排版風格)，均不包含小括號 (即 ( 和 ))，且不可出現 , 和 ; 這樣的分隔符號 (separator)
`BBB` 為 `identifier` , `CCC` , `DDD` , `EEE` , `FFF` 均為以 `list_` 開頭的巨集 (macro)

## 作答

### AAA & BBB

透過 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 可以看到關於 `list_first_entry` 的說明

/**
 * list_first_entry() - Get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 *
 * Return: @type pointer of first entry in list
 */

所以可以知道 `AAA = item` , `BBB = list`

### CCC & DDD & EEE

從程式的邏輯可以看出先取出 `queue` 中的第一個 `elements` 作為 `pivot` 並把他從原先的 `list` 裡面移除。 之後在走遍 `list` 裏面每一個 `element` 依照其 `i` 值，若比 `pivot` 小置於 `list_less` 反之則置於 `list_greater` 因此可知

- `CCC = list_for_each_entry_safe(itm, is, head, list)`

- `DDD = list_move_tail(&itm->list, &list_less)`

- `EEE = list_move_tail(&itm->list, &list_less)`

## 延伸問題

# 測驗 `2`

延續上方測驗 1，參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)，將以下程式碼改寫為非遞迴 (non-recursive; iterative) 的實作:

#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

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

    while (top >= 0) {
        INIT_LIST_HEAD(&partition);
        list_splice_init(&stack[top--], &partition);
        if (!list_empty(&partition) && !list_is_singular(&partition)) {
            struct list_head list_less, list_greater;
            INIT_LIST_HEAD(&list_less);
            INIT_LIST_HEAD(&list_greater);
            struct item *pivot =
                list_first_entry(&partition, struct item, list);
            list_del(&pivot->list);
            INIT_LIST_HEAD(&pivot->list);

            struct item *itm = NULL, *is = NULL;
            GGGG (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);
            }

            HHHH (&pivot->list, &list_less);
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, IIII);
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, JJJJ);
        } else {
            top++;
            list_splice_tail(&partition, &stack[top]);
            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(KKKK);
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

作答規範:
- 全部應以最簡潔的形式撰寫，避免空白字元
- `GGGG` 和 `HHHH` 都是以 `list_` 開頭的巨集
- `IIII`, `JJJJ`, `KKKK` 都包含 `stack`，並搭配必要的 C 運算子

## 作答

### GGGG & HHHH

- `GGGG = list_for_each_entry_safe (itm, is, &partition, list)`

- `HHHH = list_move_tail (&pivot->list, &list_less)`

### GGGG & HHHH & KKKK

- `IIII` = `&stack[++top]`

- `JJJJ` = `&stack[++top]`

- `KKKK` = `&stack[top--]`

在研究程式碼的時候花了很多時間來了閱讀[原文](https://alienryderflex.com/quicksort/)所用的方法。透過 `begin[]` 與 `end[]` 去紀錄尚未排序的陣列的 `L` 與 `R`。 在這邊的版本則是

首先先初始化一個 `stack[MAX_DEPTH]` 再將 `head` 放置於 `stack[0]` 。

取出第一個 `entry` 作為 `pivot` , 依序走遍整個鏈結，將小於 `pivot` 的節點插入 `list_less` ,大於 `pivot` 的節點插入 `list_greater`

接著將 `pivot` 插入 `list_little` 的尾部，分別將 `list_greater` 至於 `stack[1]` , `list_less` 放置於 `stack[2]` 。

直到 `top >= 0` && `list_is_singular(&stack[top])` 表示 `stack[top]` 只含有一個節點，再依序回收，串回 `head` 此時這些節點便已經排序好。

## 延伸問題

# 測驗 `3`

## 作答

### LLLL

從 `XOR_COMP()` 的結構來判斷，會將計算完的結果強制轉型成 `xor_node_t *` 。 從前文可以知道 `address` 計算的方式是透過 `XOR` 的特性所以可以知道:

`LLL = ((uintptr_t)a ^ (uintptr_t)b`)

#### MMMM