# 2025q1 Homework1 (lab0) contributed by <`NeedToDebugMyLife`> {%hackmd NrmQUGbRQWemgwPfhzXj6g %} <br> ## 開發環境 ```shell $ 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: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-7700K CPU @ 4.20GHz CPU family: 6 Model: 158 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU(s) scaling MHz: 90% CPU max MHz: 4500.0000 CPU min MHz: 800.0000 BogoMIPS: 8400.00 Flags: fpu vme de pse tsc msr pae mce cx8 apic se p mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscal l nx pdpe1gb rdtscp lm constant_tsc art ar ch_perfmon pebs bts rep_good nopl xtopolog y nonstop_tsc cpuid aperfmperf pni pclmulq dq dtes64 monitor ds_cpl est tm2 ssse3 sdb g fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2 apic movbe popcnt tsc_deadline_timer aes x save avx f16c rdrand lahf_lm abm 3dnowpref etch cpuid_fault epb pti ssbd ibrs ibpb st ibp fsgsbase tsc_adjust bmi1 avx2 smep bmi 2 erms invpcid mpx rdseed adx smap clflush opt intel_pt xsaveopt xsavec xgetbv1 xsave s dtherm ida arat pln pts hwp hwp_notify h wp_act_window hwp_epp md_clear flush_l1d a rch_capabilities Caches (sum of all): L1d: 128 KiB (4 instances) L1i: 128 KiB (4 instances) L2: 1 MiB (4 instances) L3: 8 MiB (1 instance) NUMA: NUMA node(s): 1 NUMA node0 CPU(s): 0-7 Vulnerabilities: Gather data sampling: Mitigation; Microcode Itlb multihit: KVM: Mitigation: VMX unsupported L1tf: Mitigation; PTE Inversion Mds: Mitigation; Clear CPU buffers; SMT vulnera ble Meltdown: Mitigation; PTI Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnera ble Reg file data sampling: Not affected Retbleed: Mitigation; IBRS Spec rstack overflow: Not affected Spec store bypass: Mitigation; Speculative Store Bypass disab led via prctl Spectre v1: Mitigation; usercopy/swapgs barriers and _ _user pointer sanitization Spectre v2: Mitigation; IBRS; IBPB conditional; STIBP conditional; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected Srbds: Mitigation; Microcode Tsx async abort: Mitigation; TSX disabled ``` <br> ## 針對佇列操作的程式碼實作 ### `q_new` #### 程式碼 ::: spoiler 完整程式實作 ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ::: #### 實作說明 * 使用 `malloc()` 來配置記憶體空間 * 使用 `list.h` 中的 `INIT_LIST_HEAD()` 來初始化標頭節點的指標<small>(指向自己)</small> #### 特殊狀況處理 * 檢查記憶體配置是否成功，如果失敗則回傳 `NULL` ```c if (!head) return NULL; ``` <br><hr> ### `q_free` #### 程式碼 ::: spoiler 完整程式實作 ```c void q_free(struct list_head *head) { if (!head) return; struct list_head *cur = head->next; while (cur != head) { struct list_head *tmp; tmp = cur; cur = cur->next; list_del(tmp); q_release_element(list_entry(tmp, element_t, list)); } free(head); } ``` ::: #### 實作說明 :::info 使用迴圈走訪節點並釋放每個節點的記憶體空間，走訪完成後再釋放標頭節點的空間 ::: * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `queue.h` 中的 `q_release_element()` 釋出記憶體空間 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 ```c if (!head) return NULL; ``` <br><hr> ### `q_insert_head` #### 程式碼 ::: spoiler 完整程式實作 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; char *str = strdup(s); strcat(str, "\0"); element_t *node = malloc(sizeof(element_t)); // malloc failure handle if (!str) { free(node); return false; } if (!node) { free(str); return false; } node->value = str; list_add(&node->list, head); return true; } ``` ::: #### 實作說明 :::info 1. 建立一個新節點，並將節點插入到佇列的第一個位置 (`head->next`) 2. `element_t` 結構中有兩個元素 (`char* value` 以及 `struct list_head list`)，其中 `value` 是一個指標。因此在分配記憶體空間時，`value` 只有被分配到一個 `char` 的大小，所以還需要再額外分配一個記憶體空間來儲存該節點對應的字串。 ::: * 使用 `malloc()` 來配置 `node` 的記憶體空間 * 使用 `strdup()` 來配置 `value` 指向的字串記憶體空間，同時將輸入 `s` 複製到配置好的空間內 * 使用 `list.h` 中的 `list_add()` 將節點插入到佇列開頭。 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則回傳 `false` ```c if (!head) return NULL; ``` * 檢查記憶體配置是否成功，只要其中一個 <small>(`str`, `node`)</small> 配置失敗就代表節點建立失敗，需釋放已配置的空間，並回傳 `false` ```c // if str allocation fail if (!str) { free(node); return false; } // if node allocation fail if (!node) { free(str); return false; } ``` #### 問題紀錄 `strcmp` 和 `strdup` <br><hr> ### `q_insert_tail` #### 程式碼 ::: spoiler 完整程式實作 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; char *str = strdup(s); strcat(str, "\0"); element_t *node = malloc(sizeof(element_t)); // malloc failure handle if (!str) { free(node); return false; } if (!node) { free(str); return false; } node->value = str; list_add_tail(&node->list, head); return true; } ``` ::: #### 實作方式 :::info 建立一個新節點，並將節點插入到佇列的最後一個位置 (`head->prev`) ::: * 程式邏輯和 `q_insert_head()` 相同，差別在於 `q_insert_tail()` 使用 `list.h` 中的 `list_add_tail()` 將節點插入到佇列結尾。 <br><hr> ### `q_remove_head` #### 程式碼 ::: spoiler 完整程式實作 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *node = list_entry(head->next, element_t, list); char *str = strndup(node->value, bufsize - 1); strcat(str, "\0"); strncpy(sp, str, bufsize); list_del(&node->list); return node; } ``` ::: #### 實作說明 :::info 移除 (不是刪除) 佇列的第一個節點 (`head->next`)，並將移除的節點值記錄到 `sp` 內 ::: * 使用 `strndup()` 配置一個大小為 `bufsize-1` 的空間來紀錄移除節點的 `value` <small>(需要額外補上結束符號 `\0` )</small> * 使用 `strncpy()` 紀錄的 `value` 複製到 stack pointer 內 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則回傳 `NULL` * 檢查佇列是否有節點，如果沒有則回傳 `NULL` ```c if (!head || list_empty(head)) return NULL; ``` <br><hr> ### `q_remove_tail` #### 程式碼 ::: spoiler 完整程式實作 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *node = list_entry(head->prev, element_t, list); char *str = strndup(node->value, bufsize - 1); strcat(str, "\0"); strncpy(sp, str, bufsize); list_del(&node->list); return node; } ``` ::: #### 實作說明 :::info 移除 (不是刪除) 佇列的最後一個節點 (`head->prev`)，並將移除的節點值記錄到 `sp` 內 ::: * 程式邏輯和 `q_remove_head()` 相同，差別在於 `q_remove_tail()` 移除的是佇列最後一個節點 <small>(`head->prev`)</small> <br><hr> ### `q_size` #### 程式碼 ::: spoiler 完整程式實作 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; int size = 0; struct list_head *cur = head->next; while (cur != head) { size++; cur = cur->next; } return size; } ``` ::: #### 實作說明 :::info 使用迴圈對佇列做遞移檢查。每走訪一個節點，`size` 遞增 `1`，直到走訪到 `head` <small>(走訪一輪)</small> ::: * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 * 檢查佇列是否有節點，如果沒有則回傳 `NULL` ```c if (!head || list_empty(head)) return 0; ``` <br><hr> ### `q_delete_mid` #### 程式碼 ::: spoiler 完整程式實作 ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; int size = q_size(head) / 2; struct list_head *tmp = head->next; for (int i = 0; i < size; i++) tmp = tmp->next; list_del(tmp); q_release_element(list_entry(tmp, element_t, list)); return true; } ``` ::: #### 實作說明 :::info 使用迴圈對佇列做遞移檢查直到中間節點， ::: * 使用 [`q_size()/2`](#q_size) 計算佇列的中點索引 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `queue.h` 中的 `q_release_element()` 釋出記憶體空間 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則回傳 `false` * 檢查佇列是否有節點，如果沒有則回傳 `false` ```c if (!head || list_empty(head)) return false; ``` <br><hr> ### `q_delete_dup` #### 程式碼 ::: spoiler 完整程式實作 ```c bool q_delete_dup(struct list_head *head) { if (!head || list_empty(head)) return false; char *str = strdup(""); struct list_head *cur = head->next; while (cur->next != head) { struct list_head *tmp; tmp = cur; cur = cur->next; if (strcmp(list_entry(tmp, element_t, list)->value, str) == 0 || strcmp(list_entry(tmp, element_t, list)->value, list_entry(cur, element_t, list)->value) == 0) { free(str); str = strdup(list_entry(tmp, element_t, list)->value); list_del(tmp); q_release_element(list_entry(tmp, element_t, list)); } } if (strcmp(list_entry(cur, element_t, list)->value, str) == 0) { list_del(cur); q_release_element(list_entry(cur, element_t, list)); } free(str); return true; } ``` ::: #### 實作說明 :::info 1. 因為輸入的佇列皆已完成排序，所以有相同值的節點必定相鄰 2. 每次比較兩相鄰節點，如果節點值相同則刪除節點並記錄重複節點值 3. 每次更新紀錄節點值時都需要釋放並重新分配空間，因為每次紀錄的節點值長度未必相同。也無法配置固定長度的空間，因為無法確定節點值的長度上限是多少。 ::: * 使用 `strcmp()` 比較兩個節點的 `value` 是否相同 <small>(等於 `0` 時相同)</small> * 使用 `strdup()` 配置一個空間來紀錄重複節點的 `value` * 使用 `free()` 移除配置的空間 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `queue.h` 中的 `q_release_element()` 釋出記憶體空間 #### 節點比較 * 如果當前節點 <small>(`tmp`)</small> 和下一個節點值 <small>(`cur`)</small> 相同，則刪除當前節點 * 如果當前節點 <small>(`tmp`)</small> 和紀錄的字串值 <small>(`str`)</small> 相同，則刪除當前節點 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則回傳 `false` * 檢查佇列是否有節點，如果沒有則回傳 `false` ```c if (!head || list_empty(head)) return false; ``` #### 問題紀錄 * `while` 迴圈的終止條件為 `cur->next != head` 而不是 `cur != head`，是因為當 `cur` 為最後一個節點 <small>(`cur->next == head`)</small> 時，會將 `cur` 再往後移動一個節點 <small>(`cur = cur->next`)</small>，此時的 `cur` 等於 `head` <small>(`cur == head`)</small>，但因為 `head` 沒有 `value` 元素，所以執行 `list_entry(cur, element_t, list)` 時就會產生錯誤 ::: success (已解決) ⭢ 將 `str` 的初值設為 `"\0"` (或`""`) <hr> 無法將 `str` 設為 `NULL`，因為 `strcmp()` 不支援 `NULL` 的比較 ::: * 因為 `str` 的初值為 `"\0"`,在還沒檢查到重覆節點時，`str` 的值不會產生任何改變，所以在執行 `free(str)` 時會產生錯誤。因此需要再 `free(str)` 外使用一個 `if` 判斷式來做檢查 :::success (已解決) ⭢ 將 `str` 的賦值由直接指派改為使用 `strdup` 分配 <hr> 原先的寫法是直接將 `str` 的值設為 `"\0"` (或 `""` )，但會導致執行 `free(str)` 時產生錯誤 (因為沒有配置空間所以無法進行釋放)，所以需要額外的條件判斷 ![image](https://hackmd.io/_uploads/ryj_Qkviye.png) ::: * 因為 `while` 迴圈的終止條件為 `cur->next != head`，所以實際上最後一個節點不會被檢查到，如果最後一個節點也包含重複值，就無法進行刪除。因此需要在 `while` 迴圈外使用一個 `if` 判斷式來做檢查 <br><hr> ### `q_swap` #### 程式碼 ::: spoiler 完整程式實作 ```c void q_swap(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *cur = head->next; struct list_head *next = cur->next; while (cur != head && next != head) { list_del(cur); list_add(cur, next); cur = cur->next; next = cur->next; } } ``` ::: #### 實作說明 :::info 將 `cur` 節點移動 <small>(移除+插入)</small> 到下一個節點後方 <small>(`cur->next->next`)</small> 就可以實現兩節點的交換 ::: * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_is_singular()` 檢查佇列是否只包含一個節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `list.h` 中的 `list_add()` 來將移除節點插入到指定節點後方 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 * 檢查佇列是否有節點，如果沒有或只有一個節點 <small>(只有一個無法進行交換)</small> 則結束執行 ```c if (!head || list_empty(head) || list_is_singular(head)) return; ``` <br><hr> ### `q_reverse` #### 程式碼 ::: spoiler 完整程式實作 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *cur = head->prev; while (cur != head) { struct list_head *tmp; tmp = cur; cur = cur->prev; list_move_tail(tmp, head); } } ``` ::: #### 實作說明 :::info 由佇列最後一個節點 <small>(`head->prev`)</small> 向前走訪，每走訪一個節點就將該節點移動到佇列最後 ::: * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_is_singular()` 檢查佇列是否只包含一個節點 * 使用 `list.h` 中的 `list_move_tail()` 來將指定節點移動到指定節點後方 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 * 檢查佇列是否有節點，如果沒有或只有一個節點 <small>(只有一個無法進行交換)</small> 則結束執行 ```c if (!head || list_empty(head) || list_is_singular(head)) return; ``` <br><hr> ### `q_reverseK` ::: spoiler 完整程式實作 ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head)) return; int size = q_size(head); if (k > size || k < 2) return; if (k == 2) { q_swap(head); return; } struct list_head *tmp = head->next; struct list_head *cur = head->next; struct list_head *reverse_h = head->next; struct list_head *reverse_t = head->next; for (int i = 0; i < size; i++) { tmp = cur; cur = cur->next; if (i % k == k - 1) { tmp->next = head; head->prev = tmp; q_reverse(head); reverse_t->next = head->next; head->next->prev = reverse_t; if (i == k - 1) reverse_h = head->next; reverse_t = head->prev; head->next = cur; cur->prev = head; } } if (head->next != head) { reverse_t->next = head->next; head->next->prev = reverse_t; reverse_t = tmp; } head->prev = reverse_t; head->next = reverse_h; reverse_h->prev = head; reverse_t->next = head; } ``` ::: #### 實作說明 :::info 將佇列每 `K` 個節點分為一組，分別對每組做 `q_reverse()`，再將反轉後的每個佇列重新組合成一個完整的佇列 ::: * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 [`q_size()`](#q_size) 計算佇列的長度 * 使用 [`q_swap()`](#q_swap) 對兩節點做交換 * 使用 [`q_reverse()`](#q_reverse) 計算反轉節點順序 #### 特殊狀況處理 * 檢查標頭節點 head 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 * 檢查佇列是否有節點，如果沒有則結束執行 ```c if (!head || list_empty(head)) return; ``` * 檢查 `K` 值是否為合法數值，如果不是則結束執行 ```c if (k > size || k < 2) return; ``` * 如果 `k` 值大於佇列長度，則為非法數值 * 如果 `k` 值等於`1`，則不需要做交換 * 如果 `k` 值小於`1`，則為非法數值 * 檢查 `K` 值是否為 `2`，如果是則執行 [`q_swap()`](#q_swap) ```c if (k == 2) { q_swap(head); return; } ``` * 如果 `k` 值等於 `2`，效果等同執行 [`q_swap()`](#q_swap)<small>(兩兩交換)</small> <br><hr> ### `q_sort` ::: spoiler 完整程式碼 ```c void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; int counter = 0; int mid = q_size(head) / 2 - 1; struct list_head *cut = head->next; while (counter != mid) { cut = cut->next; counter++; } struct list_head head1; struct list_head head2; INIT_LIST_HEAD(&head1); INIT_LIST_HEAD(&head2); list_splice_tail(head, &head2); list_cut_position(&head1, &head2, cut); INIT_LIST_HEAD(head); q_sort(&head1, descend); q_sort(&head2, descend); const char *str1 = NULL; const char *str2 = NULL; struct list_head *tmp; struct list_head *cur1 = (&head1)->next; struct list_head *cur2 = (&head2)->next; while (cur1 != &head1 && cur2 != &head2) { str1 = list_entry(cur1, element_t, list)->value; str2 = list_entry(cur2, element_t, list)->value; if (descend) { if (strcmp(str1, str2) >= 0) { tmp = cur1; cur1 = cur1->next; } else { tmp = cur2; cur2 = cur2->next; } } else { if (strcmp(str1, str2) <= 0) { tmp = cur1; cur1 = cur1->next; } else { tmp = cur2; cur2 = cur2->next; } } list_del(tmp); list_add_tail(tmp, head); } list_splice_tail(&head1, head); list_splice_tail(&head2, head); } ``` ::: #### 實作說明 :::info 1. 以 `merge sort` 演算法進行實作 2. 將佇列由中點分割為兩個部分，並對每個子佇列遞迴使用 `merge sort`，直到佇列長度等於 `1`。使用兩個指標從兩個子佇列標頭節點分別向後走訪，比較當前節點值大小，並依據 `descend` 對節點做排序，重複比較直到其中一個佇列的所有節點合併完成，最後再將剩餘的另一個佇列加到已排序好的佇列後方。 ::: * 使用 [`q_size()/2`](#q_size) 計算佇列的中點索引 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_is_singular()` 檢查佇列是否只包含一個節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `list.h` 中的 `INIT_LIST_HEAD()` 初始化節點 * 使用 `list.h` 中的 `list_splice_tail()` 將一佇列的所有節點移動到另一佇列的後方 * 使用 `list.h` 中的 `list_add_tail()` 來將指定節點移動到指定節點後方 * 使用 `list.h` 中的 `list_cut_position()` 將佇列分割為兩個子佇列 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `strcmp()` 比較兩個節點的 `value` 是否相同 <small>(等於 `0` 時相同)</small> #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_size))</small>，如果不存在則結束執行 * 檢查佇列是否有節點，如果沒有或只有一個節點 <small>(只有一個無法進行交換)</small> 則結束執行 ```c if (!head || list_empty(head) || list_is_singular(head)) return; ``` #### 節點比較 * 如果排序方法為 descend <small>(`descend == true`)</small>，則刪除當前比較節點中的最大值 * 如果排序方法為 ascend <small>(`descend == false`)</small>，則刪除當前比較節點中的最小值 #### 問題紀錄 * 實作方式採用遞迴對佇列作分割 <small>(呼叫 [`q_sort()`](#q_sort))</small>，因為 [`q_sort()`](#q_sort) 的第一個參數為一指向佇列的標頭節點 <small>(`struct list_head *head`)</small>，所以需要額外串接一個 `list_head` 標頭節點到子佇列上。因為本題無法使用 `malloc()` 來，所以需要將原佇列的 `head` 節點串接到子佇列上才能使用 `q_sort()`。<br> 因為使用了比較暴力了方法來將標頭節點串接到子佇列上 <small>(只對第一個節點和標頭節點做串接)</small>，所以串接後的子佇列就不是一個雙向環狀鏈結串列了。因此也沒辦法使用 `list_splice_tail` 函式，只能使用迴圈逐個串接節點。 :::success (已解決) ⭢ 使用靜態宣告的方式宣告兩個暫時的標頭節點 <hr> 宣告兩個暫時的標頭節點 `head1` 和 `head2`，用來串接分割的兩個子佇列 <small>(作為子佇列的標頭節點)</small>，以利佇列遞迴呼叫 `q_sort()` ![image](https://hackmd.io/_uploads/SyRUBO_s1l.png) <br>因為有標頭節點的存在，所以可以直接使用 `list_splice_tail` 函式直接將剩餘的子佇列所有節點直接接到已排序好的佇列後方 <small>(取代原先使用迴圈逐個搬動節點)</small> ![image](https://hackmd.io/_uploads/Hy4T7dosye.png) :::spoiler 原程式碼 (使用搬動 `head` 節點的方式) ```c void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head) || list_is_singular(head)) return; int counter = 0; int half = q_size(head) / 2; const char *str1 = NULL; const char *str2 = NULL; struct list_head *tmp; struct list_head *cur1; struct list_head *cur2; struct list_head *cut = head->next; while (counter != half) { cut = cut->next; counter++; } tmp = head->prev; head->prev = cut->prev; cut->prev->next = head; q_sort(head, descend); cur1 = head->next; head->prev = tmp; head->next = cut; cut->prev = head; tmp->next = head; q_sort(head, descend); cur2 = head->next; INIT_LIST_HEAD(head); while (cur1 != head && cur2 != head) { str1 = list_entry(cur1, element_t, list)->value; str2 = list_entry(cur2, element_t, list)->value; if (descend) { if (strcmp(str1, str2) >= 0) { tmp = cur1; cur1 = cur1->next; } else { tmp = cur2; cur2 = cur2->next; } } else { if (strcmp(str1, str2) <= 0) { tmp = cur1; cur1 = cur1->next; } else { tmp = cur2; cur2 = cur2->next; } } list_add_tail(tmp, head); } while (cur1 != head) { tmp = cur1; cur1 = cur1->next; list_add_tail(tmp, head); } while (cur2 != head) { tmp = cur2; cur2 = cur2->next; list_add_tail(tmp, head); } } ``` ::: * 在比較兩佇列的節點值時，會出現其中一個佇列的節點先被移除完的情況，這時就無法繼續執行節點值的比較 * 如果是佇列1的節點先被移除完 ➩ 將佇列2的剩餘節點依序移動到已排序佇列 * 如果是佇列2的節點先被移除完 ➩ 將佇列1的剩餘節點依序移動到已排序佇列 因為上述兩種狀況皆可能發生，所以需要額外的判斷式來檢查哪個佇列才是已完全移除的佇列。 :::success (已解決) ⭢ 移除 `if` 條件判斷 <hr> 在重新查看 `list.h` 中的 `list_splice_tail` 函式後，注意到函式內有著這一段程式: ```c static inline void list_splice_tail(struct list_head *list, struct list_head *head) { struct list_head *head_last = head->prev; ... // ⭣ if (list_empty(list)) return; ... } ``` 可以發現輸入的佇列如果為空，就會直接結束函式的執行。 因此這一部分的檢查是可以直接省略的。 ![image](https://hackmd.io/_uploads/rkeKDKjoJe.png) ::: <br><hr> ### `q_ascend` #### 程式碼 ::: spoiler 完整程式實作 ```c int q_ascend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *tmp; struct list_head *cur = head->prev; char *min = strdup(list_entry(cur, element_t, list)->value); while (cur != head) { tmp = cur; cur = cur->prev; if (strcmp(list_entry(tmp, element_t, list)->value, min) > 0) { list_del(tmp); q_release_element(list_entry(tmp, element_t, list)); } else { free(min); min = strdup(list_entry(tmp, element_t, list)->value); } } free(min); return q_size(head); } ``` ::: #### 實作說明 :::info 1. 由佇列最後一個節點 <small>(`head->prev`)</small> 向前走訪，並以最一個節點值作為整個佇列的最大值 2. 佇列的每個節點值都必須小於左側的每一個節點值 ::: * 使用 `strdup()` 配置一個空間來紀錄當前檢查到的當前最小值 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `queue.h` 中的 `q_release_element()` 釋出記憶體空間 * 使用 `free()` 移除已配置的空間 * 使用 [`q_size()`](#q_size) 計算最終佇列的長度 #### 節點比較 * 如果當前節點 (`tmp`) 小於等於當前紀錄最小值節點值 (`min`)，則將最小節點值更新為當前節點值 (`tmp = min`) * 如果當前節點 (`tmp`) 大於當前紀錄最小值節點值 (`min`)，則刪除當前節點 #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_new))</small>，如果不存在則回傳 `0` * 檢查佇列是否有節點，如果沒有則回傳 `0` ```c if (!head || list_empty(head)) return 0; ``` <br><hr><br> ### `q_descend` #### 程式碼 ::: spoiler 完整程式實作 ```c= int q_descend(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *tmp; struct list_head *cur = head->prev; char *max = strdup(list_entry(cur, element_t, list)->value); while (cur != head) { tmp = cur; cur = cur->prev; if (strcmp(list_entry(tmp, element_t, list)->value, max) < 0) { list_del(tmp); q_release_element(list_entry(tmp, element_t, list)); } else { free(max); max = strdup(list_entry(tmp, element_t, list)->value); } } free(max); return q_size(head); } ``` ::: #### 實作說明 :::info 1. 由佇列最後一個節點 <small>(`head->prev`)</small> 向前走訪，並以最一個節點值作為整個佇列的最小值 2. 佇列的每個節點值都必須大於左側的每一個節點值 ::: * 程式邏輯和 `q_ascend()` 相同，差別在於 `q_descend()` 刪除的是比當前紀錄最大節點值 (`max`) 大的節點 <br><hr> ### `q_merge` #### 程式碼 ::: spoiler 完整程式實作 ```c int q_merge(struct list_head *head, bool descend) { if (!head || list_empty(head)) return 0; if (list_is_singular(head)) return q_size(list_entry(head->next, queue_contex_t, chain)->q); int total = 0; struct list_head result; struct list_head *cur = head->next; INIT_LIST_HEAD(&result); while (cur != head) { total += list_entry(cur, queue_contex_t, chain)->size; cur = cur->next; } for (int i = 0; i < total; i++) { cur = head->next; while (list_empty(list_entry(cur, queue_contex_t, chain)->q) && cur != head) cur = cur->next; queue_contex_t *context_cur = list_entry(cur, queue_contex_t, chain); queue_contex_t *context_max = list_entry(cur, queue_contex_t, chain); queue_contex_t *context_min = list_entry(cur, queue_contex_t, chain); const element_t *element_cur; const element_t *element_max = list_entry(context_cur->q->next, element_t, list); const element_t *element_min = list_entry(context_cur->q->next, element_t, list); while (cur != head) { context_cur = list_entry(cur, queue_contex_t, chain); if (context_cur->size != 0) { element_cur = list_entry(context_cur->q->next, element_t, list); if (descend) { if (strcmp(element_cur->value, element_max->value) > 0) { element_max = element_cur; context_max = context_cur; } } else { if (strcmp(element_cur->value, element_min->value) < 0) { element_min = element_cur; context_min = context_cur; } } } cur = cur->next; } struct list_head *node; if (descend) { node = context_max->q->next; context_max->size--; } else { node = context_min->q->next; context_min->size--; } list_del(node); list_add_tail(node, &result); } list_splice_tail_init(&result, list_entry(head->next, queue_contex_t, chain)->q); int size = q_size(list_entry(head->next, queue_contex_t, chain)->q); list_entry(cur, queue_contex_t, chain)->size = size; return size; } ``` ::: #### 實作說明 :::info 1. 使用靜態配置分配一個暫時的標頭節點 <small>(`result`)</small>。由第一個子佇列向後走訪，比較所有子佇列的第一個節點，並找出當前的最小(大)節點值。找出後將該節點從對應子佇列中移除，並插入到暫時的佇列中，同時將對應子佇列的 `size` 值減 `1`。重複比較直到所有節點都已加到暫時的佇列中。最後再將暫時佇列中的所有節點搬動到第一個子佇列。 2. 使用2個 `element_t` 的指標和2個 `queue_contex_t` 的指標來記錄當前最小(大)節點以及節點所在的 `queue_context` ::: * 使用 [`q_size()`](#q_size) 計算佇列的長度 * 使用 `list.h` 中的 `list_empty()` 檢查佇列是否為空 * 使用 `list.h` 中的 `list_is_singular()` 檢查佇列是否只包含一個節點 * 使用 `list.h` 中的 `list_entry()` 取得對應節點 * 使用 `list.h` 中的 `INIT_LIST_HEAD()` 初始化節點 * 使用 `list.h` 中的 `list_del()` 來移除指定節點 * 使用 `list.h` 中的 `list_add_tail()` 來將指定節點移動到指定節點後方 * 使用 `list.h` 中的 `list_splice_tail()` 將一佇列的所有節點移動到另一佇列的後方 * 使用 `list.h` 中的 `list_splice_tail_init()` 將一佇列的所有節點移動到另一佇列的後方並初始化原佇列的標頭節點 * 使用 `strcmp()` 比較兩個節點的 `value` 是否相同 <small>(等於 `0` 時相同)</small> #### 特殊狀況處理 * 檢查標頭節點 `head` 是否存在 <small>(是否已執行 [`q_new()`](#q_new))</small>，如果不存在則回傳 `0` * 檢查是否有子佇列，如果沒有則回傳 `0` ```c if (!head || list_empty(head)) return 0; ``` * 檢查是否只有一個子佇列，如果只有一個則回傳子佇列的長度 ```c if (list_is_singular(head)) return q_size(list_entry(head->next, queue_contex_t, chain)->q); ``` #### 節點比較 * 如果排序方法為 descend <small>(`descend == true`)</small>，則將當前比較節點中的最大節點加入暫時佇列的最尾端，並將最大節點所在的 `queue_contex_t` 的 `size` 減 `1` * 如果排序方法為 ascend <small>(`descend == false`)</small>，則將當前比較節點中的最小節點加入暫時佇列的最尾端，並將最小節點所在的 `queue_contex_t` 的 `size` 減 `1` <br><hr> ### make test result :::success 100/100 ![image](https://hackmd.io/_uploads/H1vA5wsi1g.png) :::