2022q1 Homework1 (lab0)

--- tags: linux, kernel --- # 2022q1 Homework1 (lab0) contributed by < `Destiny0504` > ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 43 bits physical, 48 bits virtual CPU(s): 16 On-line CPU(s) list: 0-15 Thread(s) per core: 2 Core(s) per socket: 8 Socket(s): 1 NUMA node(s): 1 Vendor ID: AuthenticAMD CPU family: 23 Model: 113 Model name: AMD Ryzen 7 3700X 8-Core Processor Stepping: 0 Frequency boost: enabled CPU MHz: 2200.000 CPU max MHz: 4426.1709 CPU min MHz: 2200.0000 BogoMIPS: 7186.24 Virtualization: AMD-V L1d cache: 256 KiB L1i cache: 256 KiB L2 cache: 4 MiB L3 cache: 32 MiB NUMA node0 CPU(s): 0-15 ``` ## 針對佇列的操作 ### q_new > commit 7183b8e 初始化 queue ``` c struct list_head *q_new() { struct list_head *tmp; tmp->next = tmp; tmp->prev = tmp; return tmp; } ``` > commit c747f08 - 加入防止 head 為 NULL 的情況 ``` c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); /* If malloc failed, return NULL. */ if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` :::danger 不要只張貼程式碼，要解說和列出後續的改進。在 GitHub 上都有 commit 提交日期，你不需要在此標注日期。不要輕易說 "done"，工程總有可持續改進之處。 :notes: jserv ::: ### q_insert_head > commit 7183b8e 創造一個新的 node 加入整個 queue 的開頭 - 如果成功加入新的 node 會回傳 ture , 反之則回傳 false 。 ``` c bool q_insert_head(struct list_head *head, char *s) { int s_len = sizeof(s); if (!head) return false; element_t *tmp_node = malloc(sizeof(element_t)); tmp_node->value = malloc(sizeof(s)); memset(tmp_node->value, '\0', s_len); strncpy(tmp_node->value, s, strlen(s)); INIT_LIST_HEAD(&tmp_node->list); list_add(&tmp_node->list, head); return true; } ``` > commit 7e331e1 - 前面的 function 在 implement 的時候 string copy 的時候少算了 '\0' ``` c bool q_insert_head(struct list_head *head, char *s) { int s_len = sizeof(char) * strlen(s) + 1; if (!head) return false; element_t *tmp_node = malloc(sizeof(element_t)); tmp_node->value = malloc(s_len); memset(tmp_node->value, 0, s_len); strncpy(tmp_node->value, s, strlen(s) + 1); INIT_LIST_HEAD(&tmp_node->list); list_add(&tmp_node->list, head); return true; } ``` > commit 05a5ad4 - 前面的 function 沒有考慮到 malloc 失敗之後要釋放掉所有已經 allocate 的記憶體。 ``` c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *tmp_node = malloc(sizeof(element_t)); if (!tmp_node) return false; int s_len = sizeof(char) * strlen(s) + 1; tmp_node->value = malloc(s_len); if (!tmp_node->value) { q_release_element(tmp_node); return false; } memset(tmp_node->value, 0, s_len); strncpy(tmp_node->value, s, strlen(s) + 1); INIT_LIST_HEAD(&tmp_node->list); list_add(&tmp_node->list, head); return true; } ``` ### q_remove_head > commit 7183b8e 移除整個 queue 中的第一個 node - 如果整個 queue 為空，則會回傳 NULL 。（由第一個 if 判條件進行判斷 ) - 如果 sp 為 NULL，則會因為無法確定要 remove 的 string 是什麼，所以回傳 NULL 。（由第二個 if 判條件進行判斷 ) ``` c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (head->next == head) return NULL; if (sp == NULL) return NULL; element_t *tmp_node = container_of(head->next, element_t, list); strncpy(sp, tmp_node->value, bufsize - 1); list_del(head->next); return tmp_node; } ``` > commit c747f08 - 加入 remove head quiet 功能 ``` c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *tmp_node = container_of(head->next, element_t, list); if (sp) strncpy(sp, tmp_node->value, bufsize - 1); list_del(head->next); return tmp_node; } ``` > commit 05a5ad4 - truncate 多餘的字元 ``` c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *tmp_node = container_of(head->next, element_t, list); if (sp) { /* avoid to delete a string which is longer than the given bufsize */ strncpy(sp, tmp_node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->next); return tmp_node; } ``` ### q_size > commit 7183b8e 計算目前 queue 中有多少 node - 回傳值為 queue 中 node 的數量 ``` c int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ### q_free > commit 05a5ad4 釋放所有 allocated 的記憶體 ``` c void q_free(struct list_head *l) { if (l == NULL) return; element_t *cur_node = NULL, *next_node = NULL; list_for_each_entry_safe (cur_node, next_node, l, list) q_release_element(cur_node); free(l); } ``` ### q_delete_mid > commit 4e06235 刪除正中間的的 node - 如果整個 queue 為空，則會回傳 false 。（由第一個 if 判條件進行判斷 ) - 如果成功刪除會回傳 true ，否則回傳 false 。 :::spoiler 待解決問題 - 需要搞清楚為什麼我們需要多創造出一個 node 來刪除 list_head 的 pointer（因為要刪除整個 node ，所以需要一個 pointer 指向整個 node ） ::: ``` c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (head->next == head) return false; struct list_head *tmp = head->next; int counter = 0; if (q_size(head) % 2) counter = (q_size(head) - 1) / 2; else counter = q_size(head) / 2; for (; counter > 0; counter--) { tmp = tmp->next; } list_del(tmp); element_t *tmp_node = container_of(tmp, element_t, list); q_release_element(tmp_node); return true; } ``` ### q_remove_tail > commit 4e06235 移除整個 queue 中的最後一個 node - 如果整個 queue 為空，則會回傳 NULL 。（由第一個 if 判條件進行判斷 ) - 如果 sp 為 NULL，則會因為無法確定要 remove 的 string 是什麼，所以回傳 NULL 。（由第二個 if 判條件進行判斷 ) ``` c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (head->next == head) return NULL; if (sp == NULL) return NULL; element_t *tmp_node = container_of(head->next, element_t, list); strncpy(sp, tmp_node->value, bufsize - 1); list_del(head->next); return tmp_node; } ``` > commit 05a5ad4 - truncate 多餘的字元 ``` c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (list_empty(head)) return NULL; element_t *tmp_node = container_of(head->prev, element_t, list); if (sp) { /* avoid to delete a string which is longer than the given bufsize */ strncpy(sp, tmp_node->value, bufsize - 1); sp[bufsize - 1] = '\0'; } list_del(head->prev); return tmp_node; } ``` ### q_insert_tail > commit 4e06235 創造一個新的 node 加入整個 queue 的結尾。 - 如果成功在尾端加入新的 node 會回傳 ture , 反之則回傳 false 。 ``` c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (head->prev == head) return NULL; if (sp == NULL) return NULL; element_t *tmp_node = container_of(head->prev, element_t, list); strncpy(sp, tmp_node->value, bufsize - 1); list_del(head->prev); return tmp_node; } ``` > commit 7e331e1 - 前面的 function 在 implement 的時候 string copy 的時候少算了 '\0' ``` c bool q_insert_tail(struct list_head *head, char *s) { int s_len = sizeof(char) * strlen(s) + 1; if (!head) return false; element_t *tmp_node = malloc(sizeof(element_t)); tmp_node->value = malloc(s_len); memset(tmp_node->value, 0, s_len); strncpy(tmp_node->value, s, strlen(s) + 1); INIT_LIST_HEAD(&tmp_node->list); list_add_tail(&tmp_node->list, head); return true; } ``` > commit 05a5ad4 - 前面的 function 沒有考慮到 malloc 失敗之後要釋放掉所有已經 allocate 的記憶體。 ``` c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *tmp_node = malloc(sizeof(element_t)); if (!tmp_node) return false; int s_len = sizeof(char) * strlen(s) + 1; tmp_node->value = malloc(s_len); if (!tmp_node->value) { q_release_element(tmp_node); return false; } memset(tmp_node->value, 0, s_len); strncpy(tmp_node->value, s, strlen(s) + 1); INIT_LIST_HEAD(&tmp_node->list); list_add_tail(&tmp_node->list, head); return true; } ``` ### q_reverse > commit 7e331e1 - 此函式用以反轉佇列所有節點的順序 ``` c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *tmp = NULL, *next = head; // swapping the data for (; tmp != head; next = tmp) { tmp = next->next; next->next = next->prev; next->prev = tmp; } } ``` ### q_sort > commit 05a5ad4 此函式透過將最後一筆對 head 的連結打斷，將原本的雙向佇列改為單向，並傳入 merge sort function 進行排序，最後將排序好的 queue 回復為雙向佇列。 ```c void q_sort(struct list_head *head) { if (!head || list_is_singular(head) || list_empty(head)) return; struct list_head *cur = NULL; head->prev->next = NULL; head->next = mergesort(head->next); head->next->prev = head; list_for_each (cur, head) { if (!cur->next) { cur->next = head; cur->next->prev = cur; } else cur->next->prev = cur; } } ``` merge > commit 05a5ad4 此函式將兩條以排序完的 queue 依照 data 的大小順序合併為一個新的 queue 。 - 回傳值為一個 pointer 指向**合併完成**的 queue 的第一筆資料。 ``` c struct list_head *merge(struct list_head *l1, struct list_head *l2) { struct list_head *tmp = NULL, *head = NULL; if (strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value) < 0) { tmp = l1; head = l1; l1 = l1->next; } else { tmp = l2; head = l2; l2 = l2->next; } while (l1 && l2) { if (strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value) < 0) { tmp->next = l1; tmp = tmp->next; l1 = l1->next; } else { tmp->next = l2; tmp = tmp->next; l2 = l2->next; } } if (l1) tmp->next = l1; if (l2) tmp->next = l2; return head; } ``` mergesort > commit 05a5ad4 此函式將 queue 中的 data 切割成只包含一筆 data 的 list ，再交由 merge function 將 data 按照大小順序合併。 - 回傳值為一個 pointer 指向**排序完成**的 queue 的第一筆資料 - 為了確保無論何種情況下，排序的時間複雜度皆為 $\operatorname{O}(nlogn)$ ，所以選擇使用 merge sort 演算法進行排序。 ``` c struct list_head *mergesort(struct list_head *head) { // merge sort if (!head || !head->next) return head; struct list_head *fast = head->next; struct list_head *slow = head; // split list while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } fast = slow->next; slow->next = NULL; // sort each list struct list_head *l1 = mergesort(head); struct list_head *l2 = mergesort(fast); // merge sorted l1 and sorted l2 return merge(l1, l2); } ``` :::warning 善用 List APIs 改寫上述程式碼。使用通順的漢語書寫，日後你在面試場合，可能會不經意說出過去寫下的話語，現在就開始要求！ :notes: jserv ::: - 在 github 上面通過所有的 test ![](https://i.imgur.com/3KjkwvU.png) ### q_shuffle 此函式將 queue 中的 data 依照 Fisher–Yates shuffle 演算法隨機 shuffle - Fisher–Yates shuffle 演算法的優勢在於可以在 $\operatorname{O}(n)$ 的時間複雜度下完成 shuffle ``` c void q_shuffle(struct list_head *head) { srand(time(NULL)); // 用 q_size 得出整個 queue 的大小 int len = q_size(head); // 將 indirect pointer 指向 queue 的第一個 data struct list_head **indirect = &head->next; while (len) { // 決定第幾個 node 要放到 tail int random = rand() % len; indirect = &head->next; // 找出要放到 tail 的 node while (random--) indirect = &(*indirect)->next; list_move_tail(*indirect, head); len--; } } ``` ## Reference [Merger sort implementation](https://npes87184.github.io/2015-09-12-linkedListSort/)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.