--- tags: Linux, C --- # 2023q1 Homework1 (quiz1) contributed by <[huanginch](https://github.com/huanginch/)> >[題目](https://hackmd.io/@sysprog/linux2023-quiz1) ## 測驗一 ### struct item ```c #include <stdint.h> #include "list.h" struct item { uint16_t i; struct list_head list; }; ``` 此段程式碼為宣告item結構，item 包含一個數值 i 與一個嵌入至 item 的 list_head。 ### cmpint ```c 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 ```c if (list_empty(head) || list_is_singular(head)) return; ``` 首先此段程式碼判斷 list 是否為 empty 或只有一個節點，是的話就直接 return (不需要 sort )。 ```c 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。 ```c struct item *pivot = list_first_entry(head, AAA, BBB); ``` 使用 list_first_entry 巨集從 head (也就是我們的排序目標) 取得第一個節點，並將 pivot 指向此節點。 參考 [list_first_entry](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_first_entry)的說明可以得知，此巨集第二個參數需要自訂 struct 的名稱，也就是 `struct item`，第三個變數為這個 struct 中 `list_head` 的名稱，也就是 `list`。 :::info 此處 AAA 要填入 ```sruct item```， BBB 要填入 ```list``` ::: ```c list_del(&pivot->list); ``` 將 pivot 的 list 移走，因為在做quick sort 時，pivot 會重新連接 list_less 和 list_greater，所以舊的指向的 list 必須移除。 ```c 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文件](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.list_for_each_entry_safe) :::info CCC 要填入 `list_for_each_entry_safe` DDD 要填入 `list_add` EEE 要填入 `list_add` ::: #### stable sorting :::warning 為了實現 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$。 ```c list_qsort(&list_less); list_qsort(&list_greater); ``` 這兩段程式碼有錯，這邊該執行的是遞迴呼叫 list_sort 以排序剛剛分好的兩個 list。 ```c list_sort(&list_less); list_sort(&list_greater); ``` 以上才是正確寫法。 ```c 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 :::info FFF 要填入 `list_splice_tail` :::