---
# System prepended metadata

title: 2021q2 Homework2 (quiz2)

---

# 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);
}
```
顧名思義，就是檢查是否為單一節點，檢查方式就是看此節點的前後節點是否剛好都是自己。
