# 2019q1 Homework3 (review) contributed by <`flawless0714`> ## 作業要求 * 從 [第 1 週](https://hackmd.io/s/SyrZMGYr4), [第 2 週](https://hackmd.io/s/H1Pik8M8E), [第 3 週(上)](https://hackmd.io/s/S1weT4iLE), [第 3 週(下)](https://hackmd.io/s/SkrVSKiU4), [第 4 週(上)](https://hackmd.io/s/H1KLoTEv4), [第 4 週(下)](https://hackmd.io/s/BJKk1ANv4) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」 * 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗== * 若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問 :::info 像是這樣標註提問 ::: ## 題目 ### 第三週 (上) 測驗 `3` 考慮以下 linked list 程式: ```clike #include <stddef.h> struct node { int data; struct node *next; } *head; void insert(struct node *newt) { struct node *node = head, *prev = NULL; while (node != NULL && node->data < newt->data) { prev = node; node = node->next; } newt->next = node; if (prev == NULL) head = newt; else prev->next = newt; } ``` 可透過以下 pointer to pointer 改寫 `insert` 函式，功能等價但更簡潔，如下: ```clike void insert(struct node *newt) { struct node **link = &head; while (*link && A) B; newt->next = *link; *link = newt; ``` 請補完程式碼。 :::success 延伸問題: 在 Linux 核心找出運用類似的手法的程式碼並解說 ::: #### 講解 - 答案 - A = `(*link)->data < newt->data` - B = `link = &(*link)->next;` - 解說 未修改與修改過的程式碼的 while 部份不應同時檢查是否 list 已到尾巴與對 node 資料比大小，因為到尾巴時對 node (相當於空指標)做 dereference 會發生 seg fault。以下開始說明答案思路，由於 link 為 pointer to pointer，所以當做一次 dereference 時是取出 `head` 這個指標的==內容==，當我們取出內容後即可開始對其中的成員做 dereference 以取得 `data` 之資料。另外 `(*link)` 會使用小括號的原因是因為要先拿到 `head` 的內容，假如沒有括號的話會被編譯器當成對 link 這個 struct 中的成員 `data` 做 dereference，而事實上 link 並不是 struct，所以編譯時期編譯器就會跳 error 了。接下來是答案 `B` 的解說，由於 `link` 為 pointer to pointer，所以顧名思義其所儲存的內容就該是 address of pointer，所以當我們要往下一個節點走訪時就必須要使用 `&(*link)->next`，概念跟答案 `A` 雷同，首先 `*link` 取得 `head` 的內容，接下來搭配 address of 運算子就可取得當下節點中儲存著下一個節點的指標的記憶體位置。而最後一行(`*link = newt;`)的 `link` 中儲存的是 `newt` 插入後的前個節點(前面我們走訪時除了 `head` 其餘都是使用 struct 中的成員 `next`)，所以要插入新節點時直接 assign `newt` 這個指標給 `link` (即為指標 `next`)即可將新舊節點串起來。 - 延伸問題 使用此[程式碼](https://elixir.bootlin.com/linux/v4.15.18/source/block/bfq-wf2q.c#L366)來做舉例: ```clike static void bfq_insert(struct rb_root *root, struct bfq_entity *entity) { struct bfq_entity *entry; struct rb_node **node = &root->rb_node; struct rb_node *parent = NULL; while (*node) { parent = *node; entry = rb_entry(parent, struct bfq_entity, rb_node); if (bfq_gt(entry->finish, entity->finish)) node = &parent->rb_left; else node = &parent->rb_right; } rb_link_node(&entity->rb_node, parent, node); rb_insert_color(&entity->rb_node, root); entity->tree = root; } static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) { node->__rb_parent_color = (unsigned long)parent; node->rb_left = node->rb_right = NULL; *rb_link = node; } ``` 考慮上述程式碼，首先將欲插入的 tree 的根節點放入 `**node` 中，接下來開始在整棵樹中走訪，走訪時首先先將當前節點 `*node` 放到 `parent`，接下來使用 `container_of` 取得 struct 本體位置，接著將本體與新節點放入 `bfq_gt()` 比較完成時間(`bfq_entity.finish`)，若新節點的 `finish` 小於當前節點，則 `node` 將往當前節點的 left child 走訪，反之則往 right child 走訪。走到 leaf node (`*node == NULL`) 後則開始進行節點的插入作業，呼叫 `rb_link_node()` 時傳入欲插入之新節點、儲存著當前節點的 `rb_node` 的 `parent` 以及儲存著左或右節點的位置的 pointer to pointer (`**node`)，進來後首先為新節點的 `__rb_parent_color` 染上 parent 的顏色，由於 `rb_node` 的第一個成員就是顏色成員(`unsigned long __rb_parent_color`)的關西，所以我們對指標直接做 cast 即可取出顏色資料，再來就是初始化新節點的孩子(初始化為空節點)。這個函數的最後一步為整個插入的關鍵，對 `rb_link` 做 dereference 即取出儲存著左或右節點的記憶體位置，接著將 `node` (儲存新節點位置的指標)的內容 assign 到這個記憶體位置，到此已經完成新節點的插入。出來後接著進入 `rb_insert_color()` 這個函數主要是在為新節點的 child node 上色，但裡面實做不簡單...，主要功能是不要讓 tree 的 root 是紅色或是有兩個連續的紅色節點，為了達成這些目標裡面對 tree 對了一系列的翻轉，直到目標達成才出來，細節有待研究...。return 後我們將新節點的成員 `tree` assign 當前 tree 的 root，以此表示這個節點已經隸屬於一顆樹。 ### 第 ###### tags: `linux2019`