Try   HackMD

2021q1 Homework2 (quiz2)

contributed by < mickey30606 >

測驗 1

list.h

#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 使用。
突然發現下面有清楚的解釋。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這樣就可以知道原本這個 struct 的位址。


struct list_head { struct list_head *prev, *next; };

建立一個 struct 的型別,用來作為 doubly-linked list 的節點。


#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

宣告一個 list_head 然後初始化,將兩邊都指向自己。







p1



list_head

 

head

 



list_head:f0->list_head





list_head:f2->list_head






static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; }

初始化一個空的 list_head 。


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 的最尾端。







p1



newnode

 

node

 



prev

 

n

 



newnode:newp->prev:prn






head

 

head

 



newnode:newn->head:hp






dotp

...



dotp->prev:prp






dotn

...



dotp->dotn






prev:prn->head:hp






next

 

1

 



head:hn->next:np






next:nn->dotn







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 中刪除。







p



dotp

...



prev

 

prev

 



dotp->prev:pp






mainnode

 

node

 



prev:pn->mainnode:np






next

 

next

 



prev:pn->next:np






mainnode:nn->next:np






dotn

...



next:nn->dotn







static inline int list_empty(const struct list_head *head) { return (head->next == head); }

檢查這個 doubly-linked list 中是不是沒有任何 node 。


static inline int list_is_singular(const struct list_head *head) { return (!list_empty(head) && head->prev == head->next); }

檢查這個 doubly-linked list 中是不是只有一個 node 。


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 的尾端。
這兩個:







p



hpre

 

Hp

 



head

 

head

 



hpre:n->head:p






hnext

 

Hn

 



hpre:p->hnext:n






head:n->hnext:p












l



hpre

 

Lp

 



head

 

list

 



hpre:n->head:p






hnext

 

Ln

 



hpre:p->hnext:n






head:n->hnext:p






會變成:







both



hp

 

Hp

 



lp

 

Lp

 



hp:n->lp:p






ln

 

Ln

 



lp:n->ln:p






head

 

head

 



ln:n->head:p






hn

 

Hn

 



head:n->hn:p






hn:n->hp:p






list 指到的 list_head 被拿掉了!


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 裡面。

這邊沒有檢查 list_head *head_to 是否有東西感覺很危險??

切割前:







p



head_from

 

head_from

 



A

 

A

 



head_from:n->A:p






B

 

B

 



A:n->B:p






n

 

node

 



B:n->n:p






C

 

C

 



n:n->C:p






D

 

D

 



C:n->D:p






D:n->head_from:p






切割後:







pp



head_from

 

head_from

 



C

 

C

 



head_from:n->C:p






D

 

D

 



C:n->D:p






D:n->head_from:p












n



head_to

 

head_to

 



A

 

A

 



head_to:n->A:p






B

 

B

 



A:n->B:p






n

 

node

 



B:n->n:p






n:n->head_to:p







#define list_entry(node, type, member) container_of(node, type, member)

用來計算 node 所存在的 structure 的位址。


#define list_first_entry(head, type, member) \ list_entry((head)->next, type, member)

用來計算第一個 node 所存在的 structure 的位址。


#define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next)

跑過這個 linked list 中所有的 node 。

q1.h

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 == listfast->next->next == list


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); }