2023q1 Homework1 (quiz1)

contributed by < kart81604 >

注意細節！

jserv

測驗一

AAA = item
BBB = list
CCC = list_for_each_entry_safe
DDD = list_move_tail
EEE = list_move_tail
FFF = list_splice_tail

程式碼運作原理

參數介紹 :
pivot : queue 中第一個元素，拿來做比較。
list_less : 小於 pivot 的 item 會接上此 queue 。
list_greater : 大於等於 pivot 的 item 會接上此 queue 。

將 input 的 queue 的第一個 item 作為 pivot ，再將比 pivot 小的 item 組成新的 list_less queue ，其餘的為 list_greater queue 。

再利用遞迴，對這兩個 queue 進行排序，這邊展示排序 list_less 。

這邊的 list_less' 跟 list_greater' ，與第一輪的不同。

排序完成後回到第一輪，再將兩者組合起來。

---

測驗二

GGGG = list_for_each_entry_safe
HHHH = list_add_tail
IIII = stack[++top]
JJJJ = stack[++top]
KKKK = stack[top--]

程式碼運作原理

參數介紹 :
partition : 用作對於 stack 最上面非空且非單的 queue ，進行分割。
pivot : queue中的第一個元素當作比較的依據。
list_less : 將 queue 中小於 pivot 的插入此 queue 的第一個。
list_greater : 將 queue 中大於等於 pivot 的插入此 queue 的第一個。

下方的列舉 (即 - 開頭的項目) 非必要，使用簡潔且清晰的描述。

jserv

好的，已更改

在進到第一個 while 迴圈之前，建立了一個 list_head 陣列 stack ，再將 input 的 queue 接到 stack[0] 上面。(圖僅列舉有連結 queue 的部分，且 queue 是用doubly-linked list 連結，下圖應注意所連結的 queue 的狀態)

進入 while 迴圈，初始化 partition ，然後將 stack 最上面的 queue 接到 partition 後面。
(紅色表示 pivot )

如果 partition 不為空且不為單，則初始化 list_less 跟 list_greater ，將 partition 所接的 queue 的第一個獨立出來作為 pivot ，對 queue 中每個值做比較，比 pivot 小的接到 list_less ， 大於等於就接到 list_greater ，然後將剛剛獨立出來的 pivot 接到 list_less 的 tail ，接著將 list_greater 跟 list_less 接到 stack 上。

如果 partition 為空或為單，則把 stack 最上面的queue，接到 head 的後面。

---

測驗三

LLLL = (uintptr_t)(a) ^ (uintptr_t)(b)
MMMM = &list->tail 或 node
PPPP = real_next->cmp

程式碼運作原理

藉由 xorlist_for_each 的程式碼，其中的參數 rp 代表目前所指的點， node 指的是 rp 的下一個點， rn 指的是 node 的下一個點，也就是 rp 的下下一個點， rn 藉由
address_of(rp, node->cmp) 來得到node 下一個點的記憶體地址。