2023q1 Homework1 (quiz1)

contributed by <huanginch>

題目

測驗一

struct item

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

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

此段程式碼為宣告item結構，item 包含一個數值 i 與一個嵌入至 item 的 list_head。

cmpint

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

此段程式碼進行節點的大小比較，透過相減的方式，若 i1 的值大於 i2 會回傳正數(i1 - i2 > 0)，小於回傳負數(i1 - i2 < 0)，相等則回傳 0。

list_sort

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

首先此段程式碼判斷 list 是否為 empty 或只有一個節點，是的話就直接 return (不需要 sort )。

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

使用 INIT_LIST_HEAD 這個巨集來產生 list_less 與 list_greater 兩個 list，分別用來儲存小於 pivot 的 list 與大於 pivot 的 list。

struct item *pivot = list_first_entry(head, AAA, BBB);

使用 list_first_entry 巨集從 head (也就是我們的排序目標) 取得第一個節點，並將 pivot 指向此節點。

參考 list_first_entry的說明可以得知，此巨集第二個參數需要自訂 struct 的名稱，也就是 struct item，第三個變數為這個 struct 中 list_head 的名稱，也就是 list。

此處 AAA 要填入 sruct item， BBB 要填入 list

list_del(&pivot->list);

將 pivot 的 list 移走，因為在做quick sort 時，pivot 會重新連接 list_less 和 list_greater，所以舊的指向的 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);
    }

這段在做 quick sort 中的比大小，針對目標 list (head) 中的每個節點，如果值比 pivot 的值小就放入 list_less，大於或等於放入 list_greater。

同時依照傳入的參數來判斷，CCC使用的是 list_for_each_entry_safe
需傳入四個參數，其中前兩個分別用途為 *itm 作為 cursor、*is 用來做 temporary storage。
可參考 API文件

CCC 要填入 list_for_each_entry_safe
DDD 要填入 list_add
EEE 要填入 list_add

stable sorting

為了實現 stable sorting ，值與 pivot 相等的節點不能放入 list_less

考慮以下情況:

因為我們使用 head list 中的第一個節點當作 pivot，同時他的值為3，我們暫時將它稱為

$3_1$，此時 head 中第二個節點的值也是3，我們暫時稱它為

$3_2$，而 stable sorting 所要求的是排序後的 list 也能維持

$3_1$,

$3_2$的順序，因為我們排序後會依照 list_less、pivot、list_greater的順序連上，所以假設我們將等於 pviot 的值放入 list_less，會導致

$3_2$,

$3_1$。

list_qsort(&list_less);
list_qsort(&list_greater);

這兩段程式碼有錯，這邊該執行的是遞迴呼叫 list_sort 以排序剛剛分好的兩個 list。

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

以上才是正確寫法。

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

最後將排序好的 list_less、pviot、list_greater 依照順序接上，就會得到排序好的 list。

• 因為 pivot 是一個節點，所以使用 list_add
• 因為要將 list_less 接在 head 之前，所以使用 list_splice
• 因為要將 list_greater 接在 head 之後，所以使用 list_splice_tail

FFF 要填入 list_splice_tail