# 2021q1 Homework2 (quiz2)
contributed by < [`lofoz`](https://github.com/lofoz) >
###### tags: `linux2021`
> [2021 年第 2 週隨堂測驗題目](https://hackmd.io/@sysprog/linux2021-quiz2)
---
## 測驗 1
### 程式碼解析 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
### Structure
#### list_head
:::spoiler Code
```cpp
struct list_head {
struct list_head *prev, *next;
};
```
:::
:::spoiler 圖例
```graphviz
digraph list_head {
node[shape=Mrecord]
list_head [label="prev|next", xlabel="list_head"]
}
```
:::
### Functions
#### INIT_LIST_HEAD
:::spoiler Code
```cpp
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
:::
:::spoiler 圖例
```graphviz
digraph list_head {
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head"]
head:f0 -> head
head:f1 -> head
}
```
:::
#### list_add_tail
新增 node 到 list
:::warning
需要清楚新增節點的擺放位置，參照 Linux 核心原始程式碼裡頭的註解來說明
:notes: jserv
:::
:::spoiler Code
```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;
}
```
:::
:::spoiler 圖例(一個節點)
```graphviz
digraph list_head {
nodesep=1.0
rankdir="TB"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head|prev"]
t [label="<f0> prev|<f1> next", xlabel="node", fillcolor="lightblue", style="filled, bold"]
head:f1 -> t [color="red"]
t:f1 -> head [color="lightblue"]
t:f0 -> head [color="lightblue"]
head:f0 -> t [color="orange"]
}
```
:::
:::spoiler 圖例(兩個節點以上)
```graphviz
digraph list_head {
nodesep=1.0
rankdir="LR"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head"]
t1 [label="<f0> prev|<f1> next", xlabel="t1|prev"]
head:f1 -> t1
t1:f1 -> head [color="red"]
t1:f0 -> head
head:f0 -> t1 [color="orange"]
}
```
```graphviz
digraph list_head {
nodesep=1.7
rankdir="LR"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head"]
t1 [label="<f0> prev|<f1> next", xlabel="t1|prev"]
t2 [label="<f0> prev|<f1> next", xlabel="node", fillcolor="lightblue", style="filled, bold"]
head:f1 -> t1
t1:f1 -> t2 [color="red"]
t2:f1 -> head [color="lightblue"]
head:f0 -> t2 [color="orange"]
t2:f0 -> t1 [color="lightblue"]
t1:f0 -> head
}
```
:::
#### list_del
將 node 從 list 刪除
:::spoiler Code
```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;
}
```
:::
:::spoiler 圖例
```graphviz
digraph list_head {
nodesep=1.7
rankdir="LR"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head|prev"]
t1 [label="<f0> prev|<f1> next", xlabel="t1|node", fillcolor="lightblue", style="filled, bold"]
t2 [label="<f0> prev|<f1> next", xlabel="t2|next"]
head:f1 -> t1 [color="orange"]
t1:f1 -> t2
t2:f1 -> head
head:f0 -> t2
t2:f0 -> t1 [color="red"]
t1:f0 -> head
}
```
```graphviz
digraph list_head {
nodesep=1.0
rankdir="LR"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head|prev"]
t2 [label="<f0> prev|<f1> next", xlabel="t2|next"]
t2:f1 -> head
head:f0 -> t2
head:f1 -> t2 [color="orange"]
t2:f0 -> head [color="red"]
}
```
:::
#### list_splice_tail
將 list 接到 head 尾端
:::spoiler Code
```cpp
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;
}
```
:::
::: spoiler 圖例(未連接)
```graphviz
digraph list_head {
nodesep=0.2
rankdir="LR"
node[shape=Mrecord]
list [label="<f0> prev|<f1> next", xlabel="list"]
l1 [label="<f0> prev|<f1> next", xlabel="l1|\nlist_first ", style="filled, bold", fillcolor="#42AB91"]
l2 [label="<f0> prev|<f1> next", xlabel="l2|\nlist_last ", style="filled, bold", fillcolor="#F19C9F"]
list:f1 -> l1
l1:f1 -> l2
l2:f1 -> list [color="orange"]
list:f0 -> l2
l2:f0 -> l1
l1:f0 -> list [color="green"]
head [label="<f0> prev|<f1> next", xlabel="head"]
h1 [label="<f0> prev|<f1> next", xlabel="h1"]
h2 [label="<f0> prev|<f1> next", xlabel="h2|\nhead_last", style="filled, bold", fillcolor="#C4D700"]
head:f1 -> h1
h1:f1 -> h2
h2:f1 -> head [color="#7BB99B"]
head:f0 -> h2 [color="red"]
h2:f0 -> h1
h1:f0 -> head
}
```
:::
:::spoiler 圖例(連接)
```graphviz
digraph list_head {
nodesep=0.2
rankdir="LR"
node[shape=Mrecord]
head [label="<f0> prev|<f1> next", xlabel="head"]
h1 [label="<f0> prev|<f1> next", xlabel="h1"]
h2 [label="<f0> prev|<f1> next", xlabel="h2|\nhead_last", style="filled, bold", fillcolor="#C4D700"]
l1 [label="<f0> prev|<f1> next", xlabel="l1|\nlist_first ", style="filled, bold", fillcolor="#42AB91"]
l2 [label="<f0> prev|<f1> next", xlabel="l2|\nlist_last ", style="filled, bold", fillcolor="#F19C9F"]
head:f1 -> h1
h1:f1 -> h2
h2:f1 -> l1 [color="#7BB99B"]
head:f0 -> l2 [color="red"]
h2:f0 -> h1
h1:f0 -> head
l1:f1 -> l2
l2:f0 -> l1
l2:f1 -> head [color="orange"]
l1:f0 -> h2 [color="green"]
}
```
:::
#### list_cut_position
把 head_from 在 node 的位置分成兩半。
將 head_from_first 到 node 連接到 head_to，head_from 連接 node 後的節點。
:::spoiler Code
```cpp
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;
}
```
:::
:::spoiler 圖例(未切割)
```graphviz
digraph list_head {
nodesep=0.7
rankdir="LR"
node[shape=Mrecord]
head_to [label="<f0> prev|<f1> next", xlabel="head_to"]
head_from [label="<f0> prev|<f1> next", xlabel="head_from"]
h1 [label="<f0> prev|<f1> next", xlabel="h1|head_from_first"]
h2 [label="<f0> prev|<f1> next", xlabel="h2|node", style="filled, bold", fillcolor="#F19C9F"]
h3 [label="<f0> prev|<f1> next", xlabel="h3"]
h4 [label="<f0> prev|<f1> next", xlabel="h4"]
head_from:f1 -> h1 [color="red"]
h1:f1 -> h2
h2:f1 -> h3 [color="green"]
h3:f1 -> h4
h4:f1 -> head_from
head_from:f0 -> h4
h4:f0 -> h3
h3:f0 -> h2 [color="orange"]
h2:f0 -> h1
h1:f0 -> head_from [color="#7BB99B"]
}
```
:::
:::spoiler 圖例(切割後)
```graphviz
digraph list_head {
nodesep=0.1
rankdir="LR"
node[shape=Mrecord]
head_to [label="<f0> prev|<f1> next", xlabel="head_to"]
head_from [label="<f0> prev|<f1> next", xlabel="head_from"]
h1 [label="<f0> prev|<f1> next", xlabel="h1|head_from_first"]
h2 [label="<f0> prev|<f1> next", xlabel="h2|node", style="filled, bold", fillcolor="#F19C9F"]
h3 [label="<f0> prev|<f1> next", xlabel="h3"]
h4 [label="<f0> prev|<f1> next", xlabel="h4"]
head_from:f1 -> h3 [color="red"]
h1:f1 -> h2
h2:f1 -> head_to [color="green"]
h3:f1 -> h4
h4:f1 -> head_from
head_to:f1 -> h1
head_from:f0 -> h4
h4:f0 -> h3
h3:f0 -> head_from [color="orange"]
h2:f0 -> h1
h1:f0 -> head_to [color="#7BB99B"]
head_to:f0 -> h2
}
```
:::
---
### 運作原理 : merge sort ( doubly-linked list version )
### Structures
#### queue_t
:::spoiler {state="open"} Code
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
struct list_head list;
} queue_t;
```
:::
:::spoiler {state="open"} 圖例
```graphviz
digraph queue_t {
nodesep=0.1
rankdir="LR"
node[shape=Mrecord]
queue_t [label="{<f0> head|<f1> tail}|<f2> size|<f3> list", xlabel="queue_t", style="filled, bold", fillcolor="#F19C9F"]
}
```
:::
#### list_ele_t
:::spoiler {state="open"} Code
```cpp
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
```
:::
:::spoiler {state="open"} 圖例
```graphviz
digraph list_ele_t {
nodesep=0.1
rankdir="LR"
node[shape=Mrecord]
__element [label="<f0> value|<f1> next|<f2> list", xlabel="list_ele_t", style="filled, bold", fillcolor="lightblue"]
}
```
:::
### Functions
#### q_new
:::spoiler {state="open"} Code
```cpp
static queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q) return NULL;
q->head = q->tail = NULL;
q->size = 0;
INIT_LIST_HEAD(&q->list);
return q;
}
```
:::
:::spoiler {state="open"} 圖例
```graphviz
digraph q_new {
nodesep=0.5
rankdir="TB"
node[shape=Mrecord]
q [label="{{<f0> head|<f1> tail}|{<f2> size = 0}|{<f3> list}}", xlabel="q", style="filled, bold", fillcolor="#F19C9F"]
list_ele_t_1 [label="<f0> NULL", color="white"]
list_ele_t_2 [label="<f0> NULL", color="white"]
q:f0 -> list_ele_t_1
q:f1 -> list_ele_t_2
head [label="<f0> prev|<f1> next", xlabel="q->list"]
head:f0 -> head
head:f1 -> head
q:f3 -> head
}
```
:::
#### q_insert_head
將字串 s 放到 queue q->head (以 list_ele_t 而言，從 head 插入)，並將其放到 list_head (以 list_head 而言，從 tail 插入)。
:::spoiler Code
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (!q) return false;
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
char *new_value = strdup(s);
if (!new_value) {
free(newh);
return false;
}
newh->value = new_value;
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size++;
list_add_tail(&newh->list, &q->list);
return true;
}
```
:::
:::spoiler 圖例 ( size = 0 插入 )
```graphviz
digraph q_new {
nodesep=1.0
rankdir="TB"
node[shape=Mrecord]
q [label="{{<f0> head|<f1> tail}|{<f2> size = 1}|{<f3> prev|<f4> next}}", xlabel="q", style="filled, bold", fillcolor="#F19C9F"]
NULL [label="<f0> NULL", color="white"]
q:f0 -> newh
q:f1 -> newh
q:f3 -> newh
q:f4 -> newh
newh [label="{<f0> value = s|<f1> next|{<f2> prev|<f3> next}}", xlabel="newh", style="filled, bold", fillcolor="lightblue"]
newh:f1 -> NULL
newh:f2 -> q:f2
newh:f3 -> q:f2
}
```
:::
:::spoiler 圖例 ( size = 1 插入 )
```graphviz
digraph q_new {
nodesep=1.0
rankdir="LR"
node[shape=Mrecord]
q [label="{{<f0> head|<f1> tail}|{<f2> size = 2}|{<f3> prev|<f4> next}}", xlabel="q", style="filled, bold", fillcolor="#F19C9F"]
NULL [label="<f0> NULL", color="white"]
q:f0 -> newh
q:f1 -> t1
q:f3 -> newh
q:f4 -> t1
t1 [label="{<f0> value = s|<f1> next|{<f2> prev|<f3> next}}", xlabel="t1"]
t1:f1 -> NULL
t1:f2 -> q:f2
t1:f3 -> newh
newh [label="{<f0> value = s|<f1> next|{<f2> prev|<f3> next}}", xlabel="newh", style="filled, bold", fillcolor="lightblue"]
newh:f1 -> t1
newh:f2 -> t1
newh:f3 -> q:f2
}
```
:::
#### list_merge_sort
:::spoiler Code
```cpp
void list_merge_sort(queue_t *q)
{
if (list_is_singular(&q->list))
return;
queue_t left;
struct list_head sorted;
INIT_LIST_HEAD(&left.list);
list_cut_position(&left.list, &q->list, &(get_middle(&q->list)->list));
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);
}
```
:::
#### get_middle
:::spoiler Code
```cpp=
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (fast->next == list || fast->next->next == list)
break;
fast = fast->next->next;
}
return list_entry(slow, list_ele_t, list);
}
```
:::
---
### 改進空間
#### 1. struct list_ele_t 中的 next 為**無用處**之變數。
研
gdb追蹤code
Sign in with Wallet
Connect another wallet