# 2024q1 Homework2 (quiz1+2) contributed by < `dockyu` > ## 第一週測驗題 ### 測驗 1 ```c node_t *list_tail(node_t **left) ``` 要取得最後一個，所以 while 迴圈裡一定是一直將 `*left` 指到下一個，所以當沒有跳出迴圈情況就要將 ```c left = &((*left)->next); ``` ```c int list_length(node_t **left) ``` 也是要<s>遍歷</s> 整個鏈結串列，所以思路也是一樣的 :::danger 注意用語。 $\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary) ::: ### 測驗 2 :::danger 改進你的漢語表達。 ::: merge_force_collapse 檢查三個連續的 run ，如果 A<C 如果不符合就執行 merge_at 將中間run 作為輸入，否則將第三個作為輸入 merge_at 會呼叫 merge 合併目前的 run 和前一個 run ，而 merge 其實就是一直比較兩個 run 看哪一個比較小 所以 tail 應該要一直間接指到合併的鏈結串列的結尾，初始值 `AAAA` 為 `&head` 接著每次找到小的都會接在後面並*指到下一個*所以 `BBBB` 跟 `CCCC` 分別是 `&a->next` `&b->next` :::success 我覺得如果將指到下一個的功能移出判斷式，看起來會更簡潔 ```c tail = &(*tail)->next ``` ::: build_prev_link 的功能就是把剛剛拆開的鍊結串列重新組裝回一個完整的 doubly-linked list，前面的迴圈將中間的節點都修好，剩下頭尾還沒相接 `DDDD` 是 `tail->next` `EEEE` 是 `head->prev` stk 用來儲存 run ，如果 stk_size 只有1就代表已經何排序完成，要將鍊結串列變回 linux kernel 的格式了 <s>`FFFF` 為 `1`</s> :::danger 不用列出參考題解，專注於程式碼原理、你的洞見，還有你所發現的實作缺失。 ::: --- ## 第二週測驗題 [第二週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2#%E6%B8%AC%E9%A9%97-3) ### 測驗 1 <s>`AAAA` 為 `h->next` 跟 lab0 的 list_add 一模一樣</s> :::danger 不用列出參考題解，專注於程式碼原理、你的洞見，還有你所發現的實作缺失。 ::: hlist_for_each 是一個 macro 到最前面去看他的定義就知道第二個參數是要 head ，所以 `BBBB` 為 `heads` 每一個 hlist_node entry 都可以從 node 屬性回推 order_node 使用的是 `CCCC` `list_entry` 查看 hlist_add_head 就知道接受的第二個參數是 `struct hlist_head *` 型別， <s>所以 `DDDD` 是 `heads`</s> :::danger 不用列出參考題解，專注於程式碼原理、你的洞見，還有你所發現的實作缺失。 ::: ### 測驗 2 get 跟 put 都是把目標 move 到 list 的 head <s> `EEEE` `next->pprev` `FFFF` `link` `GGGG` `pos` `HHHH` `link` `IIII` `pos` `JJJJ` `link` `KKKK` `pos` </s> :::danger 不用列出參考題解，專注於程式碼原理、你的洞見，還有你所發現的實作缺失。 ::: ### 測驗 3 題目使用 Binary Search 來找到一個 long 裡第一個被設定的 bit 也就是一直判斷右半邊是不是0，因為 long 在不同架構下的長度不同，有可能是 64 或 32 bits 所以如果是 64 第一次就是判斷右邊32 bits ，所以 `AAAA` 是 `0xffffffff` 32 個為 1 的 bits :::danger 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利) ::: __clear_bit 函式將從 addr 儲存的位址開始數第 nr 個 bit 設為 0 BIT_MASK(nr) 回傳的是 nr 在一個 64 bits 中的位置 BIT_WORD(nr) 則是回傳處於第幾個 64 bits 知道目標 bit 在哪個位置之後就可以透過用 mask 做 and 操作的方式將它設為 0 :::danger 不要只是「舉燭」，你的洞見呢？ :::