contributed by < chiehen
>
linux2021
根據 q_insert_head 程式碼, 一個 queue 的架構大約如下:
改用 Graphviz 製圖
假設 list_from 是 head 為 head_from 的 list;
list_to 是 head 為 head_to 的 list;
將原本在 list_from 的 node 從 第一個 list_ele_t 到 node 搬至 list_to, 因此 head_from 留下 node->next 到最後
因為操作上只有使用到 其中的list node 因此圖片只展示 list node
結束函式後:
將 list 所連接的 node 接在 head 所串起的這個 list 的後面
看到這裡時覺得很奇怪, 為什麼不用處理 list 的記憶體, 仔細看才發現在宣告的時候並沒有使用到 malloc
You use malloc when you need to allocate objects that must exist beyond the lifetime of execution of the current block (where a copy-on-return would be expensive as well), or if you need to allocate memory greater than the size of that stack (ie: a 3mb local stack array is a bad idea).
C99 7.20.3 Memory management functions
The lifetime of an allocated object extends from the allocation until the deallocation.
依照這個可發現 queue_t left;
在 list_merge
後已不需要, struct list_head sorted;
則是在執行 list_splice_tail(&sorted, &q->list);
後完成任務
除了在題目中所說到的外,將 __pmember
轉型成 char* 是因為指標在進行加減時,是以 dereference 後的型態的大小作為單位, 而因為 offsetof 回傳的單位是 bytes, 因此在進行運算時先轉型成 deference 後單位同為 1 byte 的char*
pointer to zero??
func 接受一個 16 位元無號整數 N 並回傳小於或等於 N 的 power-of-2
直觀上想找到符合題目要求的值,便會想到從 MSB 開始找第一個不是零的位元(以下稱目標位元),他的數值便是所求,舉例來說:
N = 101012 = 2110 , func(N) = 1610 = 100002
N = 1000002 = 3210, func(N) = 3210 = 1000002
而配合註解可以發現,此程式透過將目標位元以下的位元都賦值為 1 , 再將此數字 +1 變可得到(目標位元+1個位元)的數值, 因此只要再又一個 bit 就是所求,舉例:
N = 101012 = 2110
而如何將目標位元以下的位元都賦值為 1, 便是測驗的部分。而以看似最難以達成的 N = 800016 (最多 0 需要被設為 1)舉例
因此能保證此方法對 16 位元能達到預期的效果
P.S. 事實上,如果最初值為 N = 800016, 會在最後 N + 1 時發生 overflow, 所以應另外做處理