2023q1 Homework1 (quiz1)

contributed by < csm1735 >

測驗 1

if (list_empty(head) || list_is_singular(head))
    return;

在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 return

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

接著宣告了 list_less 和 list_greater ，並對其做初始化

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

選擇第一個 entry 來做為 pivot ，並將其從原本的串列中刪除，我們可以看出 AAA 及 BBB 為 list_first_entry 所用到的兩個參數，而根據以下定義可知 AAA 為 struct 的型態， BBB 為成員的名稱。

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

因此 AAA = struct item ， BBB = 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);
}

這段可看出 CCC 功能為走訪所有的節點來做比較的動作並移動，且根據其傳入的參數可判斷 CCC = list_for_each_entry_safe ，這樣的選擇可以允許目前的節點被移走，對於比較動作完成後的移動有所幫助，也因此 DDD 跟 EEE 皆為用來移動的 list_move_tail ，將值小於 pivot 的節點移到 list_less ，反之則移動到 list_greater ，值得一提的是，考量到為了使得排序達到 stable 的目標，所以在這邊 DDD 跟 EEE 不能選擇用 list_move 。

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

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

最後這邊，透過遞迴呼叫 list_sort 來將 list_less 和 list_greater 排序完成後，我們需要將list_less 放在 pivot 之前，而list_greater 放在 pivot 之後，所以 FFF 選擇使用 list_splice_tail ，這樣即完成排序。

---

測驗 2

if (list_empty(head) || list_is_singular(head))
    return;

在一開始我們首先檢查串列是否為空或只有一個節點，如果是的話則不需要排序，因此直接 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]);

宣告 stack ，並透過 INIT_LIST_HEAD 將其初始化，一開始先將 head 的節點全都移進 stack

struct list_head partition;
INIT_LIST_HEAD(&partition);

while (top >= 0) {
    INIT_LIST_HEAD(&partition);
    list_splice_init(&stack[top--], &partition);

將 stack 中最頂端的 pop 出來放入 partition 中

if (!list_empty(&partition) && !list_is_singular(&partition))

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

這邊和測驗 1 類似，先宣告了 list_less 和 list_greater ，並對其做初始化，然後選擇 partition 中第一個 entry 來做為 pivot ，並將其從原本的串列中刪除。

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

這段可看出 GGGG 功能為走訪所有的節點，且根據其傳入的參數可判斷 GGGG = list_for_each_entry_safe ，而這樣的選擇可以允許目前的節點被移走，對於比較判斷完成後的移動有所幫助，將值小於 pivot 的節點移到 list_less ，反之則移動到 list_greater 。

HHHH (&pivot->list, &list_less);

我們會希望將list_less 放在 pivot 之前，因此這邊 HHHH 選擇 list_move_tail ，將 pivot 移動到 list_less 的尾端。

if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);

這段則是針對非空的 list_greater 跟 list_less 做操作，由於尚未排序完成，我們是將其 push 進 stack 中，且為先推入大的 list_greater ，再推入小的 list_less 。
因此 IIII = JJJJ = &stack[++top] 。

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

如果 partition 只有一個節點則先將其 push 到 stack中。
然後如果 top 大於等於 0 且 stack[top] 只有單個節點，將該節點做移除的動作並 INIT_LIST_HEAD 然後再從 stack 中 pop 掉，因此 KKKK = &stack[top--] 。
而被移除的節點則加入 head 的尾端。

由以上觀察可發現，越小的節點越會到 stack 的頂端，也因此被移除的節點會是尚未被排序的節點中最小的，而透過將被移除的節點加入 head 尾端的作法，等同於將節點由小到大加入尾端，因此全部加入完畢時也就是排序完成。

---

測驗 3