# 2025q1 Homework2 (quiz1+2) contributed by <`allen741`> ## 第 1 週測驗題 ### [測驗1](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-1) #### 程式脈絡 直接觀察 main 函式，一開始呼叫函式` test_suite `，而後呼叫` test_list `函式便開始進行函式` list_insert_before `的測試，第一次測試插入1000個元素在鏈結串列最前面 ``` for (size_t i = 0; i < N; i++) list_insert_before(&l, l.head, &items[i]); ``` 然後利用巨集` my_assert `檢查鏈結串列的值是否正確 ``` while (cur) { my_assert(cur->value == k, "Unexpected list item value"); k--; cur = cur->next; } ``` 第二次測試是1000個` list_item `全插入在鏈結串列最後面，一樣利用` assert `巨集檢查插入的元素的成員` value `是否和預期相同，若不同則會列印 error 訊息。 #### 解題 從題目可以看到是要實作鏈結串列的插入，且需要插入到 before 這個指標指向的元素前面，而需要回答的地方為 for 迴圈處如何遍歷鏈結串列找到 before 指標指向的元素，因此需回去重新觀察鏈結串列的資料結構才有辦法回答 ``` #include <stddef.h> typedef struct list_item { int value; struct list_item *next; } list_item_t; typedef struct { struct list_item *head; } list_t; ``` ```graphviz digraph LinkedList { node [shape=record]; list [label=" list_t | <head>head"]; item1 [label="<list_item>list_item | value | <next>next"]; item2 [label="<list_item>list_item | value | <next>next"]; list:head -> item1:list_item [label=""]; item1:next -> item2:list_item [label=""]; item2:next -> NULL [label=""]; } ``` 上面 list_item_t 的宣告讓 list_item_t 成為 struct list_item 的別名，因此之後初始化 list_item items[N]不需寫成 `struct list_item items[N]`，只需寫 `list_item_t items[N]`，這樣可以簡化程式碼。從上方圖形可以知道鏈結串列的結構名稱為 list_t，它含有一個 list_item 的指標 head 指向鏈結串列的第一個元素 list_item，而 list_item 包含變數 value 用來儲存整數資料和指標 next 用來指向下一個元素。 觀察函式 list_insert_before 內有一個指標的指標 p 作為 for 迴圈的索引，可以知道它是用來指向 list_item * ，因此只能用來指向 `head` 或是 `next`，因為題目說如果輸入參數` list_item_t *before `為` head `則插入元素到最前面，且迴圈內將 p 所指向的指標指向輸入參數` item `，可以得知 AAAA 的答案一定是 head 的地址，因此答案為`&l->head`。 因為` item `要插入到` before `的前面，因此迴圈必須在搜尋到` before `時跳出，因此` BBBB `的答案應為` before `，而` CCCC `應為 p 所指到的` list_item `的指標` next `的地址，因此為`&(*p)->next`，如此可以使原本指到` before `的指標在迴圈內改為指到` item `。 插入完` item `後需要將` item `的` next `指標指向` before `使鏈結串列完整連接，因此` DDDD `應為` item->next `或是` (*p)->next `，讓` item `能連接到` before `。 ### [測驗2](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-2) #### 程式脈絡 & 解題 題目所在的函式是要在記憶體中尋找一個` free block `，程式碼透過二元搜尋樹記錄不同大小的` free block `，透過函式` find_free_tree `找到適合的` free block `後，需要找到替代它的` block `，因此需要從它的子樹尋找` predecessor `來替代它以維持二元搜尋樹的結構。 題目是在左右子樹都存在元素的情況下尋找` predecessor `，從註解` /* Find the in-order predecessor: * This is the rightmost node in the left subtree. */ `可以知道要尋找左子樹的最右邊的元素，一開始進入` while `迴圈前已將` pred_ptr `設為左子樹的根節點，因此只需在` while `迴圈持續尋找最右邊的節點，所以` EEEE `為` (*pred_ptr)->r `才能在遇到` NULL `時跳出迴圈，而` FFFF `則為` pred_ptr `所指向的節點的右子節點的地址，因此為` &(*pred_ptr)->r `。 之後透過函式` find_predecessor_free_tree `再次搜尋` predecessor `，並使用` assert `巨集檢查是否找到的兩個` predecessor `相同，若不相同則終止程式。 最後，根據找到的` predecessor `是否是原來要移除的節點的左子節點來決定如何調整子樹，若不是的話則需要透過遞迴呼叫移除` predecessor `，因為需要從` predecessor `的左子樹尋找它的`predecessor` 另外，如果要移除的` target `只有左子樹或右子樹只需要直接將左子節點或右子節點替代原來的節點即可，最後將要移除的` target `所指向左右子節點的指標設為` NULL `即結束函式。 ### [測驗3](https://hackmd.io/@sysprog/linux2025-quiz1#%E6%B8%AC%E9%A9%97-3) #### 程式脈絡 ##### 函式` rebuild_list_link ` 題目是要在雙向鏈結串列實作非遞迴的` quicksort `，函式` rebuild_list_link `是在` quicksort `排序完後對每個節點的` prev `指標要進行重建，因為` quicksort `是以節點的` next `指標排序而不管節點的` prev `指標。透過` while `迴圈將全部的節點的` prev `指標重建後，需要再將鏈結串列的最後一個元素的` next `指標指向` head `並將` head `的` prev `指標指向最後一個元素才能完成雙向鏈結串列。 ##### 函式` quicksort ` ` quicksort `函式一開始宣告` begin[max_level] `做為儲存` left `、` pivot `、` right `未排序鏈結串列的指標陣列，` max_level `的值設為鏈結串列的2倍大小以確保當所有元素都被分在` left `或` right `時有足夠的空間進行排序。 在` while `迴圈中會以指標` L `儲存` begin[i] `指向的鏈結串列的第一個元素，以指標` R `儲存` begin[i] `最後一個元素，比較它們是否相同。 ###### 1.` L `和` R `不相同 ` begin[i] `指向的鏈結串列的元素至少有兩個，需要將所有元素和` pivot `(第一個元素)比大小後加入` left `或` right `這兩個指標所指向的鏈結串列中，最後將` left `傳給` begin[i]`，`pivot `傳給` begin[i+1] `，` right `傳給` begin[i+2] `後，繼續對` begin[i+2] `也就是` right `指向的鏈結串列做排序直到排序出整個鏈結串列中最大值的元素為止，這時，` L `才會第一次等於` R `。 ###### 2.` L `和` R `相同 ` begin[i] `指向的鏈結串列的元素只有一個，因此將它的` next `指標指向已經排序好的鏈結串列之中的最小元素` result `，再將` result `設為它自己後，繼續對` begin[i-1] `指向的鏈結串列做排序，若` begin[i-1] `指向的鏈結串列不只一個元素則會進入第一種狀況繼續分割成三個鏈結串列。 #### 解題 因為` value `會持續和鏈結串列的元素比大小，因此` HHHH `應該為` pivot `所指向的元素的值，因此答案為` list_entry(pivot,node_t,list)->value `，` n_value `會經由` IIII `不斷更新後再和` value `做比較，因此答案為用來遍歷鏈結串列的指標` n `所指向的元素的值，為` list_entry(n,node_t,list)->value `，最後` JJJJ `和` KKKK `即為` pivot `或` right `才能將結果存在` begin `陣列中，因為題目有說明會先對` right `指向的鏈結串列做排序且之後變數` i `繼續加2，因此` JJJJ `為` pivot `而` KKKK `為` right `。 ## 第 2 週測驗題 ### [測驗1](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-1) #### cmpint 實作` quicksort `的數字比較，因為傳入的參數是` void * `無法存取，因此需要強制轉型為` uint16_t * `後才能比較數字大小，這裡可以知道數字為無號16位元整數，因此範圍為0~65535 #### getnum 用來產生亂數，首先宣告3個16位元無號整數` s1 `、` s2 `、` s3 `，並初始化為2、1、1，因為前面為 static 的宣告因此只會初始化一次，之後便做以下計算 ``` s1=(s1*171)%30269 s2=(s2*172)%30307 s3=(s3*170)%30323 ``` 函式回傳的值為 s1 ^ s2 ^ s3，而且只有8位元，代表三個16位元的數經過 xor 運算後只回傳最右邊的8位元，可以知道這個函式用來產生0~255之間的亂數 #### get_unsigned16 呼叫上述` getnum `函式兩次製造16位元的亂數 #### main 對含有256個數字的陣列` value `進行隨機排序後，建立一個鏈結串列加入這些數字，再對` value `執行` qsort `快速排序，對鏈結串列執行` list_quicksort `快速排序，最後比較陣列` value `和鏈結串列的值是否相同，若不同會因為巨集` assert `終止程式 #### list_quicksort 對雙向鏈結串列進行快速排序，選擇鏈結串列第一個元素作為` pivot `，透過遞迴呼叫排序比` pivot `大和小的元素 #### 延伸問題 ##### 改進 random_shuffle_array ``` for (uint16_t i = len - 1; i > 0; i--) { uint16_t j = get_unsigned16() % (i + 1); // 在 [0, i] 範圍內選擇 uint16_t temp = operations[i]; operations[i] = operations[j]; operations[j] = temp; } ``` ##### 將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting 因為` list_move `是將元素插入到鏈結串列的第一個位置，而` list_move_tail `是插入到鏈結串列的最尾端，` list_for_each_entry_safe `會從鏈結串列的開頭開始和 pivot 比大小，因此若使用` list_move `會讓較後面的元素排在前面，造成有相同數值的元素經過排序後順序顛倒，無法滿足 stable sorting ### [測驗2](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-2) #### clz2 用來計算32位元無號整數從最左邊的位元往右遇到1之前有幾個0，` c `的範圍為0~3，用來控制` x `要提取的位元數的範圍 ``` c = 0 upper = 第 16 ~ 31 bit , lower = 第 0 ~ 15 bit c = 1 upper = 第 8 ~ 15 bit , lower = 第 0 ~ 7 bit c = 2 upper = 第 4 ~ 7 bit , lower = 第 0 ~ 3 bit c = 3 upper = 第 2 ~ 3 bit , lower = 第 0 ~ 1 bit ``` 函式會在` c `不等於3時繼續遞迴呼叫，直到最後等於3時會利用` magic `陣列計算最後第0~3位元有幾個0，如此即完成計算32位元的無號整數中從最左邊的位元往右遇到1之前有幾個0 #### sqrti 計算64位元無號整數的平方根的整數值，函式一開始先從左邊開始找出第一個數值為1的位元的索引值，若為奇數則會因為和`~1`做邏輯`and`運算而減1得到變數` shift `，之後設定64位元無號整數` m `第` shift `位的位元為1，利用二進制開平方法從最高位開始逐步逼近平方根 ``` x = 63 = 16 + 47 = 36 + 27 = 49 + 13 x = 1000 = 256 + 744 = 576 + 424 = 784 + 216 = 900 + 100 = 961 + 39 ``` 在 x = 63 時，` shift ` = 4，因此` m `為16，因為` m `< 63，因此會繼續測試是否 $6^2$=$(4+2)^2$ 會大於63，再測試 $7^2$ = $(4+2+1)^2$ =49 < 63後，可以知道63的平方根的整數值為7 在 x = 1000 時，` shift ` = 8，因此會測試$2^8$ = $16^2$ = 256 ，$24^2$=$(16+8)^2$ = 576，$28^2$=$(16+8+4)^2$ = 784，$30^2$=$(16+8+4+2)^2$ = 900，$31^2$=$(16+8+4+2+1)^2$ = 961，在` m `為 1 時961仍然小於1000，因此得到結果為31 在迴圈中，會將` m `加到` y `，因為最後的答案應為每次加到` y `的` m `的開根號，因此每次迴圈均會將` y `除以2，總共會執行$\frac{shift}{2}$次，讓` y `透過位元右移對其中不同的` m `值開根號，以 x = 1000 為例 y = 0 y = 256 y = $\frac{256}{2}$ = 128 y = $\frac{256}{2}$ + 64 = 192 y = $\frac{256}{4}$ + $\frac{64}{2}$ = 96 y = $\frac{256}{4}$ + $\frac{64}{2}$ + 16 = 112 y = $\frac{256}{8}$ + $\frac{64}{4}$ + $\frac{16}{2}$ = 56 y = $\frac{256}{8}$ + $\frac{64}{4}$ + $\frac{16}{2}$ + 4 = 60 y = $\frac{256}{16}$ + $\frac{64}{8}$ + $\frac{16}{4}$ + $\frac{4}{2}$ = 30 y = $\frac{256}{16}$ + $\frac{64}{8}$ + $\frac{16}{4}$ + $\frac{4}{2}$ + 1 = 31 這也可以驗證為何一開始要找偶數位元且每次` m `要右移2位($m \div 4$)而不是1位，因為奇數位所表達的數值無法開根號為整數且$\sqrt{2}$不是整數 #### 延伸問題 在 while 迴圈之後加入以下判斷式即可對$\sqrt{x}$向上取整數 ``` if(x > 0){ y++; } ``` ### [測驗3](https://hackmd.io/@sysprog/linux2025-quiz2#%E6%B8%AC%E9%A9%97-3) #### hash 將輸入值` value `乘上 0x61C88647後右移22個位元得到在 hash table 的索引值，其中，0x61C88647轉成有號整數為 2654435769，剛好是$2^{32}$ * $\frac{2}{1 + \sqrt{5}}$，即$2^{32}$除以黃金比例 #### map_add 將新的資料加入 hash table，不管是否有相同索引值的元素已在 hash table中，新的資料均會加入到鏈結串列的開頭而非結尾，因為此為單向鏈結串列 #### map_deinit 函式會釋放 hash table 中所有的鏈結串列，每次刪除鏈結串列的元素時，會先將元素從鏈結串列移除再釋放記憶體，也就是會把鏈結串列的頭指標改成指向下一個元素，並把下一個元素的` pprev `(指標的指標)改成指向頭指標，讓欲刪除的元素無法透過鏈結串列搜尋後才釋放記憶體，這裡不了解的地方是為何需要如此大費周章的在鏈結串列更改指標移除元素，因為函式到最後仍然會將所有的元素包括 hash table 全部刪除，為何不直接釋放記憶體就好還需要特別先從鏈結串列移除後才釋放記憶體? 可能原因: 可能是為了整個 linux kernel 的穩定性，避免指標在刪除元素後有短暫的時間指向未定義的記憶體空間 #### twoSum 一開始宣告一個 hash table，透過 for 迴圈尋找 target-nums[i] 是否在 hash table 中，若沒有則將nums[i]加入 hash table 中，如果有則代表已找到兩個數相加為 target，因此將結果存入陣列` ret `並回傳，倘若最後迴圈結束仍然沒有找到兩個數相加為 target，就會回傳空陣列。