linux2025-homework1

# 2025q1 Homework1 (lab0) contributed by <[`oh-ch`](https://github.com/oh-ch)> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 開發與實驗環境 ```bash $ gcc --version gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 43 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 24 On-line CPU(s) list: 0-23 Vendor ID: AuthenticAMD Model name: AMD Ryzen 9 3900X 12-Core Processor CPU family: 23 Model: 113 Thread(s) per core: 2 Core(s) per socket: 12 Socket(s): 1 Stepping: 0 Frequency boost: enabled CPU(s) scaling MHz: 49% CPU max MHz: 4672.0698 CPU min MHz: 2200.0000 BogoMIPS: 7586.04 ``` ## 針對佇列操作的程式碼實作 ### `q_new` 根據 [malloc(3)](https://man7.org/linux/man-pages/man3/free.3.html) 回傳值說明： > The malloc(), calloc(), realloc(), and reallocarray() functions return a pointer to the allocated memory, which is suitably aligned for any type that fits into the requested size or less. On error, these functions return NULL and set errno. 當配置記憶體失敗時，malloc 會回傳 NULL 。故必須先檢查 `head` 非 NULL 才可呼叫 `INIT_LIST_HEAD`，否則可能造成 Null pointer dereference 。 ```cpp struct list_head *q_new() { struct list_head *head = (struct list_head *) malloc(sizeof(struct list_head)); if (head) INIT_LIST_HEAD(head); return head; } ``` ### `q_free` 使用 `list.h` 中的 `list_for_each_entry_safe` 走訪每一個節點並逐一刪除並釋放記憶體，最終釋放 `head` 指標所指向的記憶體空間。因在 `list_for_each_entry` 更改佇列的內容將造成未定義行為，所以這裡必須使用 `list_for_each_entry_safe`。 ```cpp void q_free(struct list_head *head) { if (!head) return; element_t *e, *safe = NULL; list_for_each_entry_safe(e, safe, head, list) { q_release_element(e); } free(head); } ``` ### `q_insert_head` 和 `q_insert_tail` 在 `element_t` 結構體中，因 `value` 為 `char *` 型態，僅配置 `element_t` 所需記憶體僅能夠配置指標所需的記憶體。為了能夠將字串複製給節點，必須配置一記憶體空間供 `value` 指標指向。 [strdup(3)](https://man7.org/linux/man-pages/man3/strdup.3.html) 會複製字串至一透過 malloc 新配置的記憶體空間並回傳指向該記憶體的指標，並且這空間在刪除節點時也必須另外透過 free 釋放。 ```cpp bool q_insert_head(struct list_head *head, char *s) { element_t *e = (element_t *) malloc(sizeof(element_t)); if (!head || !e) return false; e->value = strdup(s); if (!e->value) { free(e); return false; } list_add(&e->list, head); return true; } bool q_insert_tail(struct list_head *head, char *s) { element_t *p = (element_t *) malloc(sizeof(element_t)); if (!head || !p) return false; p->value = strdup(s); if (!p->value) { free(p); return false; } list_add_tail(&p->list, head); return true; } ``` ### `q_remove_head` 和 `q_remove_tail` 先利用 `list.h` 提供的函式 `list_first_entry` 或 `list_last_entry` 取得欲移除元素，再使用 `list_del` 將元素移除。 ```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); list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } 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); list_del(&e->list); if (sp) { strncpy(sp, e->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return e; } ``` ### `q_size` 利用 `list_for_each` 走訪各個節點，並記錄走訪的節點數量，即可得到佇列的元素個數。 ```cpp 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_delete_mid` 使用快慢指標來取得佇列中點，並使用 `list_del` 自佇列移除與 `q_release_element` 釋放元素佔用的記憶體空間。 ```cpp bool q_delete_mid(struct list_head *head) { if ((!head) || list_empty(head)) return false; struct list_head *fast, *slow; for (fast = head->next->next, slow = head->next; fast != head && fast != head->prev; fast = fast->next->next, slow = slow->next) { } element_t *e = list_entry(slow, element_t, list); list_del(&e->list); q_release_element(e); return true; } ``` ### `q_delete_dup` 從測資中觀察到在執行 `q_delete_dup` 前都會先執行 `q_sort` ，意味著若有重複的元素，則在佇列中會是連續的。我的做法為在每走訪一個節點時先複製該字串到暫存的變數，並於後續的走訪判斷是否為相同的字串，若字串相同則刪除前一節點。原先做法在迴圈內使用 strdup 來保存用來辨別重複的字串，已知 strdup 是由呼叫 malloc 來配置記憶體空間，每次呼叫 malloc 或 free 時，可能會觸發系統呼叫（如 sbrk 或 mmap），這些系統呼叫需要從使用者層級切換到核心層級，這是一個相對昂貴的操作。後續改用固定緩衝區，在程式啟動時一次性分配，不需要頻繁的系統呼叫，因此避免了這些開銷。 ```diff bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; + char s[MAX_STR_LEN]; struct list_head *li = head->next; while (li != head && li->next != head) { element_t *e = list_entry(li, element_t, list); const element_t *e_next = list_entry(li->next, element_t, list); if (strcmp(e->value, e_next->value) == 0) { - struct list_head *prev = li->prev; - char *s = strdup(e->value); + strncpy(s, e->value, MAX_STR_LEN - 1); + s[MAX_STR_LEN - 1] = '\0'; while (strcmp(e->value, s) == 0) { li = li->next; + list_del(&e->list); q_release_element(e); if (li == head) break; e = list_entry(li, element_t, list); } - free(s); - prev->next = li; - li->prev = prev; } else li = li->next; } ``` ### `q_swap` 以兩個節點為單位，每走訪一節點，使用 `list_move` 將此節點移動到其下一節點的 `next` 指標指向的位置即完成交換。後續迴圈的指標也只需往前一元素即代表移動到新的另一兩節點。 ```cpp void q_swap(struct list_head *head) { if (!head) return; struct list_head *li = head->next; while (li != head && li->next != head) { list_move(li, li->next); li = li->next; } } ``` ### `q_reverse` 首先創建一暫存變數 `tmp` ，使用 `list_splice_init()` 將 `head` 後續的所有元素移動到 `tmp` 並將 `head` 初始化，後續再將原先存於 `tmp` 元素逐一移動到 `head->next` ，即可達到佇列反轉。 ```cpp void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; LIST_HEAD(tmp); list_splice_init(head, &tmp); while (!list_empty(&tmp)) { struct list_head *li = tmp.next; list_move(li, head); } } ``` ### `q_reverseK` 先以佇列的元素個數除以 K 求得預計反轉的次數 n ，並自 `head` 將 K 個節點轉移到暫存佇列 `tmp` ，反轉 `tmp` 的節點後再加到原先佇列的尾部，重複 n 次。最終再將剩餘不需反轉的節點移動到尾部即完成。 ```cpp void q_reverseK(struct list_head *head, int k) { int n = q_size(head) / k, r = q_size(head) % k; LIST_HEAD(tmp); for (int i = 0; i < n; i++) { struct list_head *li = head; for (int j = 0; j < k; j++) li = li->next; list_cut_position(&tmp, head, li); q_reverse(&tmp); list_splice_tail_init(&tmp, head); } for (int i = 0; i < r; i++) list_move_tail(head->next, head); } ``` ### `merge` 此函式為 `q_sort` 的輔助函式，用來將兩個開頭為 `left` 及 `right` 的子串列排序並合併到另一個開頭為 `head` 的子串列，而這裡的 `head` 為原先兩個子串列拆分前的開頭。 ```cpp void merge(struct list_head *head, struct list_head *left, struct list_head *right) { while (!list_empty(left) && !list_empty(right)) { element_t *l = list_first_entry(left, element_t, list); element_t *r = list_first_entry(right, element_t, list); if (strcmp(l->value, r->value) <= 0) list_move_tail(&l->list, head); else list_move_tail(&r->list, head); } if (list_empty(left)) list_splice_tail(right, head); else list_splice_tail(left, head); } ``` ### `merge_sort` 此函式是 `q_sort` 的輔助函式，用來將一個串列以中點為界拆分成左右兩個子串列，並將原先的開頭 `head` 初始化作爲後來儲存排序後串列的開頭。 ```cpp void merge_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *fast = head->next, *slow = head->next; while (fast->next != head && fast->next->next != head) { slow = slow->next; fast = fast->next->next; } LIST_HEAD(left); LIST_HEAD(right); list_cut_position(&left, head, slow); list_splice_tail_init(head, &right); merge_sort(&left); merge_sort(&right); merge(head, &left, &right); } ``` ### `q_sort` > [Commit 11319fd](https://github.com/sysprog21/lab0-c/commit/11319fdc15b903f6ecb25015de53d9b59f28bbb2) 實作採用遞迴 Merge Sort ，先以中點為界將佇列分成左右兩部分直到出現單一元素的子佇列後，再將佇列逐一排序後合併，最終即可完成排序。 ```cpp void q_sort(struct list_head *head, bool descend) { merge_sort(head); if (descend) q_reverse(head); } ``` ### `q_ascend` 和 `q_descend` > [Commit 05b8687](https://github.com/sysprog21/lab0-c/commit/05b8687f3cbb88532f9563f63ad867479c12c6d6) `q_ascend` 必須使佇列中的每個節點不大於其右邊的節點，否則必須刪除這個節點。需注意的是這函式刪除的對象為左邊節點，若是直接從左邊開始走訪的話，則必須每走訪一個節點就記錄起來並跟後續節點比較是否有發現嚴格小於它的值直到回到 `head` ，直觀的做法時間複雜度為 O($n^2$) 。然而若是先反轉佇列，則變成刪除的對象為右方，且只要往前走訪時確保右方節點的值 $<=$ 左方節點的值，走訪一輪直到回到 `head` 即完成刪除，最終再次反轉回到原始的順序即可完成題目要求。因 `strcmp(a, b)` 比較方式是由 a 的值減去 b 的值，並依據結果的正負值判斷大小。原先的作法是以右邊節點值減去左邊節點值，想法上較不直觀，因為比較方式是由左自右，應由左邊節點減去右邊節點才較能看出變化的趨勢，進而得知函式結果是遞增或遞減。 ```diff /* Remove every node which has a node with a strictly less value anywhere to * the right side of it */ int q_ascend(struct list_head *head) { // https://leetcode.com/problems/remove-nodes-from-linked-list/ if (!head || list_empty(head)) return 0; q_reverse(head); const char *min = NULL; struct list_head *li, *tmp; list_for_each_safe(li, tmp, head) { element_t *e = list_entry(li, element_t, list); - if (!min || strcmp(e->value, min) < 0) + if (!min || strcmp(min, e->value) >= 0) min = e->value; ``` ### `q_merge` 根據 `queue.h` 對於此函式的說明，將第二個及之後的佇列合併到第一個佇列。我的作法為先將第二及之後的佇列與第一個佇列依序合併，並且記錄佇列大小的變化。當所有佇列合併成後再呼叫 `q_sort` ，並根據 `descend` 的值排序成升序或降序。 ```cpp int q_merge(struct list_head *head, bool descend) { queue_contex_t *fqc = list_first_entry(head, queue_contex_t, chain); queue_contex_t *iqc; list_for_each_entry(iqc, head, chain) { if (iqc == fqc) continue; list_splice_init(iqc->q, fqc->q); fqc->size += iqc->size; iqc->size = 0; } q_sort(fqc->q, descend); return fqc->size; } ``` ## 研讀 lib/list_sort.c ## 亂數研究及 shuffle 實作 ## 研讀論文〈Dude, is my code constant time?〉