# 2021q1 Homework2 (quiz2)
contributed by < `mickey30606` >
## 測驗 1
### list.h
```c=
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#endif
```
因為使用 ```({})``` ,所以前面加一個 ```__extension__``` 可以不顯示 gcc 的警告訊息。
沒看過的用法 ==```__typeof__(((type *) 0)->member)```== 這個可以當 member 的 type 使用。
突然發現下面有清楚的解釋。
這樣就可以知道原本這個 struct 的位址。
---
```c=
struct list_head {
struct list_head *prev, *next;
};
```
建立一個 struct 的型別，用來作為 doubly-linked list 的節點。
---
```c=
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}
```
宣告一個 list_head 然後初始化，將兩邊都指向自己。
```graphviz
digraph p1 {
list_head [label = "<f0>|<f1>head|<f2>" shape = record ];
list_head:f0 -> list_head [arrowhead = vee, tailclip=true]
list_head:f2 -> list_head
}
```
---
```c=
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head; head->prev = head;
}
```
初始化一個空的 list_head 。
---
```c=
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;
}
```
將 node 加入整個 doubly-linked list 的最尾端。
```graphviz
digraph p1{
#subgraph nn{
#rankdir = TB
# newnode[label = "{<newp>|new node|<newn>}" shape = record]
# newnode:newn ->head:hp [dir=both]
#newnode:newp -> prev:prn [dir=both]
#}
rankdir = LR
newnode[label = "{<newp>|node|<newn>}" shape = record]
dotp[label = "..." shape = box]
prev[label = "{<prp>|n|<prn>}" shape = record]
head[label = "{<hp>|head|<hn>}" shape = record]
next[label = "{<np>|1|<nn>}" shape = record]
dotn[label = "..." shape = box]
dotp->prev:prp [dir = both]
newnode:newn ->head:hp [dir=both]
newnode:newp -> prev:prn [dir=both]
prev:prn -> head:hp [dir = both style = "dotted"]
head:hn -> next:np [dir = both]
next:nn ->dotn [ dir = both]
dotp -> dotn [dir = both]
}
```
---
```c=
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next, *prev = node->prev;
next->prev = prev; prev->next = next;
}
```
將 node 在 doubly-linked list 中刪除。
```graphviz
digraph p{
rankdir = LR
dotp[label="..." shape = box]
prev[label = "{<pp>|prev|<pn>}", shape = record]
mainnode[label = "{<np>|node|<nn>}", shape = record]
next[label = "{<np>|next|<nn>}", shape = record]
dotn[label = "..." shape = box]
dotp ->prev:pp [dir=both]
prev:pn -> next:np[dir=both]
prev:pn -> mainnode:np[dir=both, style="dotted"]
mainnode:nn -> next:np [dir=both, style="dotted"]
next:nn -> dotn [dir=both]
}
```
---
```c=
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
檢查這個 doubly-linked list 中是不是沒有任何 node 。
---
```c=
static inline int list_is_singular(const struct list_head *head)
{
return (!list_empty(head) && head->prev == head->next);
}
```
檢查這個 doubly-linked list 中是不是只有一個 node 。
---
```c=
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;
}
```
將 list 中的 node 接入 head 這個 doubly-linked list 的尾端。
這兩個:
```graphviz
digraph p{
rankdir = LR
hpre[label="{<p>|Hp|<n>}", shape = record]
head[label = "{<p>|head|<n>}", shape = record]
hnext[label = "{<p>|Hn|<n>}", shape = record]
// hdot[label = "", shape = box]
// hdotb[label="" , shape=box]
hpre:n -> head:p[dir=both]
head:n -> hnext:p [dir=both]
hpre:p -> hnext:n[dir=both]
// hpre:p->hdot[dir=both]
// hnext:n->hdotb[dir=both]
}
```
```graphviz
digraph l{
rankdir = LR
hpre[label="{<p>|Lp|<n>}", shape = record]
head[label = "{<p>|list|<n>}", shape = record]
hnext[label = "{<p>|Ln|<n>}", shape = record]
// hdot[label = "", shape = box]
// hdotb[label="" , shape=box]
hpre:n -> head:p[dir=both]
head:n -> hnext:p [dir=both]
hpre:p -> hnext:n[dir=both]
}
```
會變成:
```graphviz
digraph both{
rankdir = LR
hp[label="{<p>|Hp|<n>}", shape = record]
lp[label="{<p>|Lp|<n>}", shape = record]
ln[label="{<p>|Ln|<n>}", shape = record]
head[label="{<p>|head|<n>}", shape = record]
hn[label="{<p>|Hn|<n>}", shape = record]
hp:n->lp:p[dir=both]
lp:n->ln:p[dir=both]
ln:n->head:p[dir=both]
head:n->hn:p[dir=both]
hn:n->hp:p[dir=both]
}
```
:::warning
list 指到的 list_head 被拿掉了！
:::
---
```c=
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;
}
```
在 head_from 這個 doubly-linked list 中，以 node 為裁切點，把 node 以前的(包含 node 本身) doubly-linked list 存到 head_to 中，而其餘的仍舊待在 head_from 裡面。
:::warning
這邊沒有檢查 list_head *head_to 是否有東西感覺很危險??
:::
切割前：
```graphviz
digraph p{
rankdir=LR
head_from[label="{<p>|head_from|<n>}", shape=record]
A[label="{<p>|A|<n>}", shape = record]
B[label="{<p>|B|<n>}", shape=record]
n[label="{<p>|node|<n>}", shape = record]
C[label="{<p>|C|<n>}", shape=record]
D[label="{<p>|D|<n>}", shape=record]
head_from:n->A:p[dir=both]
A:n->B:p[dir=both]
B:n->n:p[dir=both]
n:n->C:p[dir=both]
C:n->D:p[dir=both]
D:n->head_from:p[dir=both]
}
```
切割後：
```graphviz
digraph pp{
rankdir=LR
head_from[label="{<p>|head_from|<n>}", shape=record]
C[label="{<p>|C|<n>}", shape=record]
D[label="{<p>|D|<n>}", shape=record]
head_from:n->C:p[dir=both]
C:n->D:p[dir=both]
D:n->head_from:p[dir=both]
}
```
```graphviz
digraph n{
rankdir=LR
head_to[label="{<p>|head_to|<n>}", shape = record]
A[label="{<p>|A|<n>}", shape = record]
B[label="{<p>|B|<n>}", shape=record]
n[label="{<p>|node|<n>}", shape = record]
head_to:n->A:p[dir=both]
A:n->B:p[dir=both]
B:n->n:p[dir=both]
n:n->head_to:p[dir=both]
}
```
---
```c=
#define list_entry(node, type, member) container_of(node, type, member)
```
用來計算 node 所存在的 structure 的位址。
---
```c=
#define list_first_entry(head, type, member) \
list_entry((head)->next, type, member)
```
用來計算第一個 node 所存在的 structure 的位址。
---
```c=
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
跑過這個 linked list 中所有的 node 。
### q1.h
```c=
static list_ele_t *get_middle(struct list_head *list)
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (COND1 || COND2)
break;
fast = fast->next->next;
}
return list_entry(TTT, list_ele_t, list);
}
```
用來取得 linked list 中間的 node 。
而中間迴圈的中止條件應該是要 fast 在最後一個或是倒數第二個的時候中止。
所以 COND1 和 COND2 分別為 ```fast->next == list``` 和 ```fast->next->next == list``` 。
---
```c=
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
if (list_empty(lhs)) {
list_splice_tail(lhs, head);
return;
}
if (list_empty(rhs)) {
list_splice_tail(rhs, head);
return;
}
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = list_entry(lhs->next, list_ele_t, list)->value;
char *rv = list_entry(rhs->next, list_ele_t, list)->value;
struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
list_del(tmp);
list_add_tail(tmp, head);
}
list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}
```
Sign in with Wallet
Connect another wallet