# 2021q1 Homework2 (quiz2) contributed by < `chiehen` > ###### tags:`linux2021` ## 測驗一 ### 解釋程式碼 根據 q_insert_head 程式碼, 一個 queue 的架構大約如下: ```graphviz digraph structs { node[shape=record] rankdir="LR" queue [label="<h> head|<t> tail|<f2> size|{<list> list|{<p> prev|<n> next}}"]; subgraph subs{ struct1 [label="<v> value1|<next> next|<l> list|{<p> prev|<n> next}"]; struct2 [label="<v> value2|<next> next|<l> list|{<p> prev|<n> next}"]; struct3 [label="<v> value3|<next> next|<l> list|{<p> prev|<n> next}"]; struct3:next -> struct2:next; struct2:next -> struct1:next; struct3:p -> struct2:n[dir="both", constraint=false] struct2:p -> struct1:n[dir="both", constraint=false] } queue:t -> struct1:v; queue:h -> struct3:v; queue:n -> struct1:p[dir="both" constraint=false]; queue:p -> struct3:n[dir="both" constraint=false]; } ``` :::danger 改用 Graphviz 製圖 :notes: jserv ::: * list_cut_position() ```c= /** * list_cut_position() - Move beginning of a list to another list * @head_to: pointer to the head of the list which receives nodes * @head_from: pointer to the head of the list * @node: pointer to the node in which defines the cutting point */ static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) { struct list_head *head_from_first = head_from->next; if (list_empty(head_from)) return; if (head_from == node) { INIT_LIST_HEAD(head_to); return; } head_from->next = node->next; head_from->next->prev = head_from; head_to->prev = node; node->next = head_to; head_to->next = head_from_first; head_to->next->prev = head_to; } ``` 假設 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 ```graphviz digraph structs{ node[shape=record] rankdir ="LR"; head1 [label="head from|<p> prev|<n> next"] head1:n -> node1:p [dir="both"] head1:p -> node4:n [dir="both"] subgraph subs{ node1 [label="1|{<p> prev|<n> next}"]; node2 [label="2|{<p> prev|<n> next}"]; node3 [label="3|{<p> prev|<n> next}"]; node4 [label="4|{<p> prev|<n> next}"]; node1:n -> node2:p [dir="both"] node2:n -> node3:p [dir="both"] node3:n -> node4:p [dir="both"]} } ``` 結束函式後: ```graphviz digraph structs{ node[shape=record] rankdir ="LR"; head1 [label="head from|<p> prev|<n> next"] head2 [label="head to|<p> prev|<n> next"] head2:n -> node1:p [dir="both"] head2:p -> node2:n [dir="both"] head1:n -> node3:p [dir="both"] head1:p -> node4:n [dir="both"] node1 [label="1|{<p> prev|<n> next}"]; node2 [label="2|{<p> prev|<n> next}"]; node3 [label="3|{<p> prev|<n> next}"]; node4 [label="4|{<p> prev|<n> next}"]; node1:n -> node2:p[dir="both"]; node3:n -> node4:p [dir="both"] } ``` * list_splice_tail() ```c= /** * list_splice_tail() - Add list nodes from a list to end of another list * @list: pointer to the head of the list with the node entries * @head: pointer to the head of the list */ static inline void list_splice_tail(struct list_head *list, struct list_head *head) { struct list_head *head_last = head->prev; struct list_head *list_first = list->next, *list_last = list->prev; if (list_empty(list)) return; head->prev = list_last; list_last->next = head; list_first->prev = head_last; head_last->next = list_first; } ``` 將 list 所連接的 node 接在 head 所串起的這個 list 的後面 看到這裡時覺得很奇怪, 為什麼不用處理 list 的記憶體, 仔細看才發現在宣告的時候並沒有使用到 malloc [When and why to use malloc?](https://stackoverflow.com/questions/8800482/when-and-why-to-use-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);` 後完成任務 * container of 的 macro 可以從 member 推出 struct 的記憶體起始位置 ```c= #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` 除了在[題目](https://hackmd.io/@sysprog/linux2021-quiz2)中所說到的外,將 `__pmember` 轉型成 char* 是因為指標在進行加減時,是以 dereference 後的型態的大小作為單位, 而因為 offsetof 回傳的單位是 bytes, 因此在進行運算時先轉型成 deference 後單位同為 1 byte 的char* pointer to zero?? --- ## 測驗二 ### 解釋程式碼 func 接受一個 16 位元無號整數 N 並回傳小於或等於 N 的 power-of-2 ```c= uint16_t func(uint16_t N) { /* change all right side bits to 1 */ N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; return (N + 1) >> 1; } ``` 直觀上想找到符合題目要求的值,便會想到從 MSB 開始找第一個不是零的位元(以下稱目標位元),他的數值便是所求,舉例來說: N = 10101~2~ = 21~10~ , func(N) = 16~10~ = 10000~2~ N = 100000~2~ = 32~10~, func(N) = 32~10~ = 100000~2~ 而配合註解可以發現,此程式透過將目標位元以下的位元都賦值為 1 , 再將此數字 +1 變可得到(目標位元+1個位元)的數值, 因此只要再又一個 bit 就是所求,舉例: N = 10101~2~ = 21~10~ 1. 11111~2~ 2. 100000~2~ 3. 10000~2~ = 16~10~ 而如何將目標位元以下的位元都賦值為 1, 便是測驗的部分。而以看似最難以達成的 N = 8000~16~ (最多 0 需要被設為 1)舉例 1. 因為目標位元保證為 1 ,在第三行後能保證目標位元及下一個位元都為 1, (N=C000~16~) 2. 基於上一點, 第四行則能保證目標位元及比他小的三個位元都為 1, (N = F000~16~) 3. 基於上一點, 第五行則能保證目標位元及比他小的7個位元都為 1, (N = FF00~16~) 4. 基於上一點, 第六行則能保證目標位元及比他小的15個位元都為 1, (N = FFFF~16~) 因此能保證此方法對 16 位元能達到預期的效果 P.S. 事實上,如果最初值為 N = 8000~16~, 會在最後 N + 1 時發生 overflow, 所以應另外做處理 --- ## 測驗三