# 2021q2 Homework2 (quiz2) contributed by < `William0715` > ## Topic - [ ] 程式原理:仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作 - [ ] ... - [ ] ... ## 測驗一 ### 仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作 #### 結構定義 ```cpp struct list_head { struct list_head *prev, *next; }; #define LIST_HEAD(head) struct list_head head = {&(head), &(head)} static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; } ``` 這裡是對於 head 節點的宣告與定義，這裡將 head 節點要使用的呼叫打包成一個定義，以及內部使用的 head 初始化的函數。 初始化時，不論是 next 還是 prev 都指向自己。 然後是雙向鏈結串列的元素結構定義: ``` typedef struct __element { char *value; struct __element *next; struct list_head list; } list_ele_t; typedef struct { list_ele_t *head; /* Linked list of elements */ list_ele_t *tail; size_t size; struct list_head list; } queue_t; ``` #### list_add_tail ```cpp static inline void list_add_tail(struct list_head *node, struct list_head *head) { struct list_head *prev = head->prev; prev->next = node; node->next = head; node->prev = prev; head->prev = node; } ``` 1.函數初始的連結宣告關係如以下所示: ` ```graphviz digraph linkedlist { rankdir=LR node [shape=box]; "prev" [style="filled", fillcolor=lightblue] "head" [style="filled", fillcolor="red"] "else" [label="......" shape="none"] "else2" [label="......" shape="none"] rankdir=LR { rankdir=LR "head"->"else" "prev"->"head" "else"->"head" "else2"->"prev" [label="prev"] "head"->"prev" "prev"->"else2" } } ``` 2.接著斷開原有連結，並重新連結為以下關係: ```graphviz digraph linkedlist { rankdir=LR node [shape=box]; "prev" [style="filled", fillcolor=lightblue] "head" [style="filled", fillcolor="red"] "node" [style="filled", fillcolor=green] "else" [label="......" shape="none"] "else2" [label="......" shape="none"] rankdir=LR { rankdir=LR "head"->else else2->"prev"->"node"->"head" "head"->"node" [label="prev"] "node"->"prev"->else2 else->"head" } } ``` #### list_del ```cpp static inline void list_del(struct list_head *node) { struct list_head *next = node->next, *prev = node->prev; next->prev = prev; prev->next = next; } ``` 1. 給定要移除的節點，並選定它前後的節點，如下所示: ```graphviz digraph linkedlist { rankdir=LR node [shape=box]; "prev" [style="filled", fillcolor=lightblue] "next" [style="filled", fillcolor="red"] "node" [style="filled", fillcolor=green] "else" [label="......" shape="none"] "else2" [label="......" shape="none"] rankdir=LR { rankdir=LR "node"->"next" "next"->else else2->"prev"->"node" "prev"->else2 else->"next"->"node" "node"->"prev" [label="prev"] } } ``` 2.將連結關係改為以下: ```graphviz digraph linkedlist { rankdir=LR node [shape=box]; "prev" [style="filled", fillcolor=lightblue] "next" [style="filled", fillcolor="red"] "else" [label="......" shape="none"] "else2" [label="......" shape="none"] rankdir=LR { rankdir=LR "next"->"else2" "else"->"prev"->"next" "prev"->"else" "else2"->"next"->"prev" } } ``` 從上述程式碼可以發現，這裡沒有對被移除的 node 做記憶體釋放，只是單純的移除節點。 #### list_is_singular ```cpp static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); } ``` 顧名思義，就是檢查是否為單一節點，檢查方式就是看此節點的前後節點是否剛好都是自己。