# quiz 1 測驗題

###### tags: `linux2022`

##### quicksort

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

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

順序應該改成 list_splice(&list_less, head); list_add_tail(&pivot->list, head); list_splice(&list_greater, head->prev);

##### non-recursive implement

#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); //top-- need?
        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;
            list_for_each_entry_safe (itm, is, &partition, list) {// GGGG=list_for...
                //list_del(&itm->list);
                if (cmpint(&itm->i, &pivot->i) < 0)
                    list_move(&itm->list, &list_less);
                else
                    list_move(&itm->list, &list_greater);
            }

            list_move_tail (&pivot->list, &list_less);//HHHH=lt_move_tail
            if (!list_empty(&list_greater))
                list_splice_tail(&list_greater, &stack[top]); //IIII=&stack[top]
            if (!list_empty(&list_less))
                list_splice_tail(&list_less, &stack[top]); //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(&stack[top]);//KKKK=&stack[top]
                list_add_tail(&tmp->list, head);
            }
        }
    }
}

預定最大深度為512，存入變數。檢查 head 開頭表單非空白，該表單有超過一個節點，否則停止程式。
初始化陣列各節點，指標指向自己。初始化 top, partition 等變數、節點。注意19行這裡，因為下面有檢測 partition 是否為空白表單，但本行初始化與 partition 檢測條件衝突，會導致 if 這段分支不會執行，所以先挪去，考慮是否移動到 if 代碼裡面。接下來，stack 向 partition 丟節點。我尚未弄清楚，未習慣 splice 語法，誤會它對節點沒有影響，他會使 partition 得到 stack 下面的節點之後，可以通過 if 條件，執行 if 代碼。先看 else 部份，當 partition 表單為空白或單一節點時，應該說 partition 沒有連接的點，開始這個分支，下面會再檢查 stack 是否為單一節點，但 stack 在 else 分支只接受 partition 的節點，partition 已經檢查確認無接點，所以 else 下方 while 檢查 stack 是多餘的，改動 top 但只在 else 使用也是多餘。 while 的條件和外面大迴圈 while 加上 if ，兩者是等價的，但 else 裡 while 沒有對 top 值改動，甚至 if 都沒有使用，如此一來， 可以確認 top 只在 -1, 0 之間擺動。功用不明，甚至有些像 if 條件式的回傳值，假設如此，可以清楚程式碼如何編寫。再來看 if 分支，初始化 list_less, list_greater, pivot 等節點的指標，選擇 partition 的開頭切斷指標。迴圈中，以 pivot 值區分 partition 的節點為兩表單， list_less 和 list_greater，注意到迴圈第一行 list_del 因為後面 list_move 會做一樣的事情，所以予以刪除。這個有 cmp_int 的迴圈，是用來分割表單為 list_less 和 list_greater

參考 [作業](https://hackmd.io/@willwillhi/linux2023-quiz1)不懂為什麼自己看不出來，可能不夠熟悉。