# 2024q1 Homework2 (quiz1+2) contributed by < [`hugo0406`](https://github.com/hugo0406) > ## [第一周測驗題](https://hackmd.io/@sysprog/linux2024-quiz1) ### 測驗一 ### 測驗二 --- ## [第二周測驗題](https://hackmd.io/@sysprog/linux2024-quiz2) ### 測驗一 :::warning :warning: 注意以下: 1. 避免過早逐行程式碼講解，否則很容易淪落為「舉燭」。 2. 程式碼背後的動機、考量因素，還有手法比程式碼本身，更值得在開發紀錄探討。 3. 為何給定 preorder 和 inorder，即可重建二元樹？你該探討。 ::: 給定由二個由整數構成陣列的前序 (preorder) 和中序 (inorder) 形式，分別是對同一棵二元樹的前序及中序走訪結果，藉此重建此二元樹。以下是運用 Linux 核心的 hash table 實作程式碼 :::danger 不用抄寫題目，專注探討程式原理、闡述你的洞見，還有你預期做哪些改進。 ::: hlist 用於 hash table 的實作，詳細內容請參考[Linux 核心的 hash table 實作](https://hackmd.io/@sysprog/linux-hashtable)。 hlist_head 和 hlist_node 用於 hash table 中 bucket 的實作，具有相同 hash value 的節點 (即 $hash(i) = hash(j),i\neq j$ ) 會放在同一條鏈結串列上。 值得我們注意的是 hlist_node 裡的 `**pprev` 是指標的指標，它指向的是前一個節點的 next 指標。 這樣的目的是即使要刪除的節點是 **最前面的節點** 時，也可以透過 `*pprev = next` 去直接修改指標的指向。 ```c struct order_node { struct hlist_node node; int val; int idx; }; ``` `order_node` 結構如下圖所示: ```graphviz digraph { label = "order_node" rankdir = LR; node[shape="Mrecord"]; node_1[label = "<v>val|<i>index|<h>hlist_head |{<p>pprev | <n>next}"]; } ``` ```c struct TreeNode { int val; struct TreeNode *left, *right; }; ``` `TreeNode`結構如下圖所示: ```graphviz digraph { label = "TreeNode" rankdir = LR; node[shape="Mrecord"]; node_1[label = "<m>val | {<p> left | <n>right}", group = list]; } ``` ```c static inline void INIT_HLIST_HEAD(struct hlist_head *h) { h->first = NULL; } ``` `INIT_HLIST_HEAD` 對鏈結串列的頭初始化為 NULL ，對應的圖如下: ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] NULL[shape = plaintext, label = "NULL", group = list] hlist_head:n -> NULL } ``` ```c static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { if (h->first) h->first->pprev = &n->next; n->next = AAAA; n->pprev = &h->first; h->first = n; } ``` 從函式名稱 `hlist_add_head` 不難看出要在鏈結串列的開頭加入節點 ( LIFO 準則) 首先可以看到一開始的 if 為判斷 `h->first` 是否為 NULL，若不為 NULL 則代表鏈結串列上有節點。 - 鏈結串列非空 ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list]; node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1 -> node_2 [ weight = 10, style = invis ] hlist_head:n -> node_1:m; node_1:p -> hlist_head:n; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> NULL; } ``` ```c #4 h->first->pprev = &n->next; ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list]; NULL1[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1 -> node_2 [ weight = 10, style = invis ] hlist_head:n -> node_1:m; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> NULL1; node_1:p -> node_n:n[color=red]; {rank = same; hlist_head;node_n}; } ``` ```c #5 n->next = h->first; //AAAA ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list]; node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; NULL1[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1 -> node_2 [ weight = 10, style = invis ] hlist_head:n -> node_1:m; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> NULL1; node_1:p -> node_n:n; {rank = same; hlist_head;node_n}; node_n:n -> node_1:m[color=red]; } ``` ```c #6 n->pprev = &h->first; ``` ```graphviz digraph G { rankdir = LR; //splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list]; NULL1[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1 -> node_2 [ weight = 10, style = invis ] hlist_head -> node_n [style = invis] node_n -> hlist_head [style = invis] hlist_head:n -> node_1:m; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> NULL1; node_1:p -> node_n:n; {rank=same;node_1;} node_n:n -> node_1:m; node_n:p -> hlist_head:n[color=red]; } ``` ```c #7 h->first = n; ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; node_1[label = "<m>hlist_node_1 | {<p>pprev | <n>next}", group = list]; node_2[label = "<m>hlist_node_2 | {<p>pprev | <n>next}", group = list]; NULL1[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1 -> node_2 [ weight = 10, style = invis ] hlist_head -> node_n [style = invis] node_n -> hlist_head [style = invis] hlist_head:n -> node_n:m[color=red]; node_1:n -> node_2:m; node_2:p -> node_1:n; node_2:n -> NULL1; node_1:p -> node_n:n; {rank=same;node_1;} node_n:n -> node_1:m; node_n:p -> hlist_head:n; } ``` - 鏈結串列為空 ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] NULL_1[shape = plaintext, label = "NULL", group = list] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; hlist_head:n -> NULL_1 NULL_1 -> node_n:p [style = invis] } ``` ```c #5 n->next = h->first; //AAAA ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; NULL_1[shape = plaintext, label = "NULL", group = list] hlist_head:n -> NULL_1 node_n:n ->NULL_1 [color = red] } ``` ```c #6 n->pprev = &h->first; ``` ```graphviz digraph G { rankdir = LR; //splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_n[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; NULL_1[shape = plaintext, label = "NULL", group = list] // list_head:n -> NULL_1 node_n:n ->NULL_1 node_n:p ->hlist_head:n [color=red] hlist_head:n -> NULL_1 [ headport="s" splines=curve ] {rank="min" hlist_head} } ``` ```c #7 h->first = n; ``` ```graphviz digraph G { rankdir = LR; splines = false; node[shape = "record"] hlist_head[label = "<m>hlist_head | <n>first"] node_1[label = "<m>hlist_node_n | {<p>pprev | <n>next}", group = list]; NULL[shape = plaintext, label = "NULL", group = list] {rank = "min" hlist_head} hlist_head -> node_1[ weight = 10, style = invis ] node_1:n -> NULL; node_1:p -> hlist_head:n; hlist_head:n -> node_1:m[color=red]; } ``` ```c= static int find(int num, int size, const struct hlist_head *heads) { struct hlist_node *p; int hash = (num < 0 ? -num : num) % size; hlist_for_each (p, BBBB) { struct order_node *on = CCCC(p, struct order_node, node); if (num == on->val) return on->idx; } return -1; } ``` 從函式名稱 `find` 及回傳值型態可以推測出此函示去尋找值為 num 的節點 ，並返回該節點的 idx。 首先觀察第 4 行，這邊的雜湊函數是採用 Division method ，共有 size 個 bucket，`hash` 的值為 num 所屬的第幾個 bucket ， 接下來第五行去該 bucket 所指向的鏈結串列去走訪每個節點尋找，可以看出 `BBBB = &heads[hash]` 。因為要把 `num` 與每個節點的 `val` 進行比較是否相等，需要知道 `order_node` 這個結構體起始地址，可以透過 `container_of` 這個巨集來得到 ， <s> 因此 `CCCC=container_of` 或 `CCCC=list_entry`。 </s> :::danger 不用列出參考題解，專注在程式碼的探討。 ::: ```c static inline void node_add(int val, int idx, int size, struct hlist_head *heads) { struct order_node *on = malloc(sizeof(*on)); on->val = val; on->idx = idx; int hash = (val < 0 ? -val : val) % size; hlist_add_head(&on->node, DDDD); } ``` 函式 `node_add()` 依節點的雜湊值將節點插入所屬 bucket 鏈結串列的開頭，因此 `DDDD = &heads[hash]` ```c= static struct TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) { struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads)); for (int i = 0; i < inorderSize; i++) INIT_HLIST_HEAD(&in_heads[i]); for (int i = 0; i < inorderSize; i++) node_add(inorder[i], i, inorderSize, in_heads); return dfs(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1, in_heads, inorderSize); } ``` 函示 `build_tree()` 依中序和前序建一顆二元樹，為了方便說明，假設 Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 。 首先上段程式碼會先建立一個雜湊表 ， bucket 的數量等於 inorderSize ，按照上面的假設，共有 5 個 buckets ，接下來對每個鍊節串列的頭進行初始化。 示意圖如下： ```graphviz digraph G { rankdir=LR; splines = false; node[shape=record]; map [label="hlist_head.first |<ht0> [0] |<ht1>[1] |<ht2>[2] |<ht3>[3] |<ht4>[4]"]; NULL_0,NULL_1,NULL_2,NULL_3,NULL_4[shape = plaintext,width=0.1 label = "NULL", group = list] map:ht0 -> NULL_0 map:ht1 -> NULL_1 map:ht2 -> NULL_2 map:ht3 -> NULL_3 map:ht4 -> NULL_4 } ``` 接下來依序將 inorder 裡的元素經過雜湊函數，插入其所屬的鏈結串列 示意圖如下： ```graphviz digraph G { rankdir=LR; splines=false; node[shape=record]; map [label="hlist_head.first |<ht0>[0] |<ht1>[1] |<ht2>[2] |<ht3>[3] |<ht4> [4] "]; NULL_0,NULL_1,NULL_2,NULL_3[shape = plaintext,width=0.1 label = "NULL", group = list] node[shape="Mrecord"]; node_0[label = "<v>val:9 |<i>idx:0|<h>hlist_node |{<p>pprev | <n>next}"]; node_1[label = "<v>val:3 |<i>idx:1|<h>hlist_node |{<p>pprev | <n>next}"]; node_2[label = "<v>val:15|<i>idx:2|<h>hlist_node | {<p>pprev | <n>next}"]; node_3[label = "<v>val:20|<i>idx:3|<h>hlist_node | {<p>pprev | <n>next}"]; node_4[label = "<v>val:7 |<i>idx:4|<h>hlist_node | {<p>pprev | <n>next}"]; map:ht4 -> node_0:h node_0:p ->map:ht4 node_0:n ->NULL_0 map:ht3 -> node_1:h node_1:p ->map:ht3 node_1:n ->NULL_1 map:ht0 -> node_3:h node_3:p -> map:ht0 node_3:n -> node_2:h node_2:p -> node_3:n node_2:n -> NULL_3 map:ht2 ->node_4:h node_4:p ->map:ht2 node_4:n ->NULL_2 } ``` 最後程式遞迴呼叫 `dfs()` ```c static struct TreeNode *dfs(int *preorder, int pre_low, int pre_high, int *inorder, int in_low, int in_high, struct hlist_head *in_heads, int size) { if (in_low > in_high || pre_low > pre_high) return NULL; struct TreeNode *tn = malloc(sizeof(*tn)); tn->val = preorder[pre_low]; int idx = find(preorder[pre_low], size, in_heads); tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder, in_low, idx - 1, in_heads, size); tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder, idx + 1, in_high, in_heads, size); return tn; } ``` ### 測驗二 ### 測驗三 :::danger 不用抄寫題目，專注探討程式原理、闡述你的洞見，還有你預期做哪些改進。 ::: ```c #define __const_hweight8(w) \ ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \ (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \ (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \ (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7))))) ``` 首先觀察這個巨集，拆分成多個小項進行分析。先來看 `(!!((w) & (1ULL << 0))`， w 與常數 1 進行 bitwise AND 再經過二次 NOT，根據 [C 語言的 bit-field](https://hackmd.io/@sysprog/c-bitfield) 裡所提及的，經過兩次 NOT，能確保結果一定是 0 或 1 ，若 w 的 least significant bit 為 1，則運算結果為 1 。可以歸納出 `(!!((w) & (1ULL << n))` ，若 w 的第 n 位(從低位開始) bit 為 1 ，則運算結果為 1。總結來說，這個巨集就是對 w 的 least significant byte 進行 [population count](https://en.wikichip.org/wiki/population_count#google_vignette) , `__const_hweight16(w)` 就是對最低位的兩個 BYTE 進行 popcount ，其餘以此類推。