--- tags: linux2022, linux --- # 2022q1 Homework1 (lab0) contributed by < [Julian-Chu](https://github.com/Julian-Chu) > [GitHub](https://github.com/Julian-Chu/lab0-c) ## Data type 主要使用的 struct, 與去年不同改以 Linux Doubly Linked Lists 實作 lab0 ```cpp typedef struct { char *value; struct list_head list; } element_t; struct list_head { struct list_head *prev; struct list_head *next; }; ``` ## API 操作 doubly linked list 的 API 已經包含在 lab0-c/list.h 裡面 ## 實作 ### q_new ```cpp struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (head) INIT_LIST_HEAD(head); return head; } ``` 創建一個 list_head 當作操作的基準節點, 此節點不嵌入在 element_t ### q_free ```cpp void q_free(struct list_head *l) { if (!l || list_empty(l)) { free(l); return; } element_t *entry, *n; list_for_each_entry_safe (entry, n, l, list) { list_del(&entry->list); free(entry->value); free(entry); } free(l); } ``` 使用 list API 走訪個節點釋放記憶體，需要注意釋放的記憶體有 - element_t - element_t->list - head 本身 ### q_insert_head ```cpp bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; e->value = strdup(s); if (!e->value) { free(e); return false; } list_add(&e->list, head); return true; } ``` 利用 list_add 插入節點, 注意賦值給 `e->value` 失敗的情況也需要釋放 `element_t` 的記憶體空間 ### q_insert_tail ```cpp bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *e = malloc(sizeof(element_t)); if (!e) return false; e->value = strdup(s); if (!e->value) { free(e); return false; } list_add_tail(&e->list, head); return true; } ``` 與 `q_insert_tail` 類似，改用 `list_add_tail` API ### q_remove_head ```cpp element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *e = list_first_entry(head, element_t, list); if (!e) return NULL; list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } ``` 使用 `list_first_entry` 取得節點， `list_del` 移除節點，另外還需要把節點的值輸出到 `sp`, 由於此處是字串，需要注意 `\0` 結尾，使用 `strlcpy` 會更好 ### q_remove_tail ```cpp element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *e = list_last_entry(head, element_t, list); if (!e) return NULL; list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } ``` 同上，改用 `list_last_entry` ### q_size ```cpp int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; int size = 0; struct list_head *node; list_for_each (node, head) { size++; } return size; } ``` 沒有 $O(1)$ 的需求可以直接迴圈計算，如有 $O(1)$ 需求可以在把 head 嵌入一個 struct 利用該 struct 紀錄個數 ### q_delete_mid ```cpp bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ struct list_head *slow = head->next, *fast = head->next; while (fast != head->prev && fast != head) { slow = slow->next; fast = fast->next->next; } element_t *e = list_entry(slow, element_t, list); if (!e) return false; list_del(slow); free(e->value); free(e); return true; } ``` 這邊採用單向快慢指針， 由於是 doubly linked list 也可以兩個指針分別往 prev 和 next 走，相遇點爲中點 ### q_delete_dup ```cpp bool q_delete_dup(struct list_head *head) { // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ if (!head) return false; if (list_empty(head)) return true; struct list_head **indirect = &head->next; while (*indirect != head && (*indirect)->next != head) { element_t *a = list_entry(*indirect, element_t, list); element_t *b = list_entry((*indirect)->next, element_t, list); if (strcmp(a->value, b->value) == 0) { // 需要特別檢查 b 移動到 head 的情況 while (&b->list != head && strcmp(a->value, b->value) == 0) { list_del((*indirect)->next); q_release_element(b); b = list_entry((*indirect)->next, element_t, list); } list_del(*indirect); q_release_element(a); } else { indirect = &(*indirect)->next; } } return true; } ``` 利用 pointer to pointer 實作，需要注意當 `list_entry` 接收到 `head` 情況， 會回傳 non-null 的 entry, 但 `list_entry` 不會檢查型別, 所以該 entry 是非法的 ### q_swap ```cpp void q_swap(struct list_head *head) { // https://leetcode.com/problems/swap-nodes-in-pairs/ if (!head || list_empty(head)) return; struct list_head *cur, *tmp; cur = head->next; while (cur != head && cur->next != head) { tmp = cur->next; cur->prev->next = tmp; tmp->prev = cur->prev; cur->next = tmp->next; cur->next->prev = cur; cur->prev = tmp; tmp->next = cur; cur = cur->next; } } ``` ### q_reverse ```cpp void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *cur = head, *next = head->next; do { cur->next = cur->prev; cur->prev = next; cur = next; next = cur->next; } while (cur != head); } ``` doubly linked list 實作 reverse 意外的簡單，`prev` 與 `next` 互換即可 ### q_sort ```cpp struct list_head *merge_sort_two_nodes(struct list_head *a, struct list_head *b) { if (!b) return a; if (!a) return b; struct list_head *head = NULL; struct list_head **indirect = &head; while (a && b) { element_t *entry_a = list_entry(a, element_t, list); element_t *entry_b = list_entry(b, element_t, list); if (strcmp(entry_a->value, entry_b->value) < 0) { *indirect = a; a = a->next; } else { *indirect = b; b = b->next; } indirect = &(*indirect)->next; } if (a) *indirect = a; if (b) *indirect = b; return head; } struct list_head *merge_sort(struct list_head *node) { if (!node) return NULL; if (!node->next) return node; struct list_head *slow = node, *fast = node->next; while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; } struct list_head *mid = slow->next; slow->next = NULL; struct list_head *left, *right; left = merge_sort(node); right = merge_sort(mid); return merge_sort_two_nodes(left, right); } /* Sort elements of queue in ascending order * No effect if q is NULL or empty. In addition, if q has only one * element, do nothing. */ void q_sort(struct list_head *head) { if (!head || list_empty(head)) return; head->prev->next = NULL; head->next = merge_sort(head->next); struct list_head *cur = head; while (cur->next) { cur->next->prev = cur; cur = cur->next; } cur->next = head; head->prev = cur; } ``` 切斷 doubly linked list 當成 singly linked list 就可以使用 merge sort 了， 最後重建 link 即可 ## Todo
Last changed by  
 
Julian Chu
253

Read more

2023 Homework3

contributed by < Julian-Chu >

10/8/2023
linux2023: Julian-Chu

α−1

8/12/2023
2022q1 Homework6 (ktcp)

contributed by < Julian-Chu > K08: ktcp 自我檢查清單 參照 Linux 核心模組掛載機制，解釋 $ sudo insmod khttpd.ko port=1999 這命令是如何讓 port=1999 傳遞到核心，作為核心模組初始化的參數呢？ 首先會看到 main.c 裡面對 port 參數進行宣告跟初始化 static ushort port = DEFAULT_PORT; module_param(port, ushort, S_IRUGO);

6/8/2022
2022q1 Homework1 (quiz1)

contributed by < Julian-Chu > GitHub 測驗 1 測驗 2 answer struct ListNode *deleteDuplicates(struct ListNode *head){ if(!head) return NULL;

2/27/2022
Read more from Julian Chu
Published on HackMD