--- tags: Linux Kernel --- # 2023q1 Homework1 (lab0) contributed by < [`chun61205`](https://github.com/chun61205) > ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.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) i5-1035G1 CPU @ 1.00GHz CPU family: 6 Model: 126 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 5 CPU max MHz: 3600.0000 CPU min MHz: 400.0000 BogoMIPS: 2380.80 ``` ## 資料結構 ### `element_t` :::info 圖待補 ::: ### `queue_contex_t` :::info 圖待補 ::: ## 開發過程 :::success 詳閱作業書寫規範。 :notes: jserv 已解決 ::: ### `q_size` ```c /* Create an empty queue */ 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; } ``` 走訪所有節點，已找到佇列的 `size` 。 ### `q_new` ```c /* Create an empty queue */ struct list_head *q_new() { struct list_head *head = malloc(sizeof(struct list_head)); if (head == NULL) return NULL; INIT_LIST_HEAD(head); return head; } ``` 利用 `INIT_LIST_HEAD` 來建立一個空的佇列。 ### `q_free` ```c /* Free all storage used by queue */ void q_free(struct list_head *l) { if (!l || list_empty(l)) { free(l); return; } element_t *entry, *safe; list_for_each_entry_safe (entry, safe, l, list) { q_release_element(entry); } free(l); return; } ``` 利用 `list_for_each_entry_safe` 走訪所有 `entry` ，再藉由 `q_release_element` 釋放記憶體。 ### `q_insert_head` 和 `q_insert_tail` :::danger 避免只列出程式碼，你的想法和遇到的各式開發問題，更為關鍵，HackMD 適合討論，而非張貼大量程式碼。 :notes: jserv ::: ```c /* Insert an element at head of queue */ bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *tmp = malloc(sizeof(element_t)); if (!tmp) return false; size_t s_len = strlen(s); tmp->value = malloc(s_len + 1); if (!(tmp->value)) { free(tmp); return false; } strncpy(tmp->value, s, s_len); tmp->value[s_len] = '\0'; list_add(&(tmp->list), head); return true; } /* Insert an element at tail of queue */ bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; element_t *tmp = malloc(sizeof(element_t)); if (!tmp) return false; size_t s_len = strlen(s); tmp->value = malloc(s_len + 1); if (!(tmp->value)) { free(tmp); return false; } strncpy(tmp->value, s, s_len); tmp->value[s_len] = '\0'; list_add_tail(&(tmp->list), head); return true; } ``` 生成要插入的 `entry` 後，分別藉由 `list_add` 和 `list_add_tail` 來插入 `entry` 。 :::info 實測後發現無法滿足時間複雜度 $O(1)$ 的要求，推測原因為 strncpy，預計在研究 [dudect](https://github.com/oreparaz/dudect) 工具和論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 後改善。 ::: ### `q_remove_head` 和 `q_remove_tail` ```c /* Remove an element from head of queue */ element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *target = list_first_entry(head, element_t, list); list_del(head->next); if (sp) { strncpy(sp, target->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return target; } /* Remove an element from tail of queue */ element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)) return NULL; element_t *target = list_last_entry(head, element_t, list); list_del(head->prev); if (sp) { strncpy(sp, target->value, bufsize - 1); sp[bufsize - 1] = '\0'; } return target; } ``` 兩個函式分別藉由 `list_first_entry` 和 `list_last_entry` 取得要移除的 `entry` 再藉由 `list_del` 將目標移除掉。 因為 `list_del` 會將目標前後的 `entry` 連接，因此不需要額外進行調整。 此外，這兩個函式的回傳值為 `target->value` 的值。 :::info 實測後發現無法滿足時間複雜度 $O(1)$ 的要求，推測原因為 strncpy，預計在研究 [dudect](https://github.com/oreparaz/dudect) 工具和論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf) 後改善。 ::: ### `q_delete_mid` ```c /* Delete the middle node in queue */ bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head *left = head->prev, *right = head->next; while (!(left == right) && !(right->prev == left)) { right = right->next; left = left->prev; } list_del(right); q_release_element(list_entry(right, element_t, list)); return true; } ``` 我的想法是使用左右指標，分別從左邊和右邊開始尋訪整個佇列。 如此一來，我們便需要分作兩種情況討論： 1. 節點數為單數，則代表左右指標相同時，它們所指向的便是中間的節點。 2. 節點數為複數，則代表右指標會超過一格，因此中間的節點會出現在 `right->prev == left` ### `q_delete_dup` 我的想法為 只要使用兩個連續的指標， `curr_node` 和 `next_node` ，並尋訪整個佇列，便能夠直接透過比較的方式來查看相鄰兩個節點是否有相同的值。 ```c if(strcmp((list_entry(curr_node, element_t, list))->value, (list_entry(next_node, element_t, list))->value) ``` 然而，這樣做會衍生出一個問題，就是當出現相同值得節點，並刪除其中一個的時候，下一步會無法確定是否要移除 `curr_node` 。因此我的作法為，先透過一個變數紀錄上一個節點是否需要移除。 ```c if(strcmp((list_entry(curr_node, element_t, list))->value, (list_entry(next_node, element_t, list))->value)){ //curr and next elements don't have the same value. if(last_cmp){ list_del(curr_node); q_release_element(list_entry(curr_node, element_t, list)); } last_cmp = 0; } else{ //curr and next elements have the same value; last_cmp = 1; list_del(curr_node); q_release_element(list_entry(curr_node, element_t, list)); } ``` ### `q_swap` :::warning > :warning: 不要急著說「完成」，工程是持續反省和改進的過程，目前只是 `qtest` 搭配自動評分沒有遇到 regression，不代表「完成」。再改進！ > :notes: jserv ::: ```c /* Swap every two adjacent nodes */ void q_swap(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *curr_node; list_for_each (curr_node, head) { if (curr_node->next == head) break; list_move(curr_node, curr_node->next); } return; } ``` 我的思路為，透過 `curr_node` 和 `curr_node->next` 表示要交換的兩個節點 ，接著尋訪所有節點，再利用 `list_move` 將 `curr_node` 搬移到 `curr_node->next` 前面，以實現兩個節點交換。 其實最一開始的想法是透過 `curr_node` 和 `next_node` 的操作來實現 `q_swap` ，不過在看到 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverse-%E5%AF%A6%E4%BD%9C) 的 `q_reverse` 後，我又回去重看了 `list_move` ，發現 `list_move` 不只有在移動到 `head` 時可以使用，中途的節點也可以使用，因此才有了現在的版本。 ### `q_reverse` ```c /* Reverse elements in queue */ void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *node = NULL, *safe = NULL; list_for_each_safe (node, safe, head) list_move(node, head); return; } ``` 這裡受到 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_reverse-%E5%AF%A6%E4%BD%9C) 的啟發，只要走訪所有節點，再將節點移動到佇列開頭，整個佇列就會被反轉。 ### `q_reverseK` ```c void q_reverseK(struct list_head *head, int k) { if (!head || list_empty(head) || k <= 1) return; struct list_head *node = head->next; while (1) { struct list_head *tmp = node, *curr_head = node->prev; for (int i = 0; i < k; i++, node = node->next) if (node == head) return; node = tmp; tmp = node->next; for (int i = 0; i < k; i++, node = tmp, tmp = tmp->next) list_move(node, curr_head); } } ``` 我的想法為，將每 $k$ 個節點分為一組，在確認接下來的節點不會有 `head` 後，再一個一個用 `list_move` 來將排列順序倒轉。 ### `q_sort` 和 `lib/list_sort.c` 研讀 #### `q_sort` 初步開發 我使用 merge sort 實作，實作分兩個部份，負責合併兩個佇列的 `q_merge_two` ，和負責分割佇列的 `q_sort` ： ```c list_for_each_safe(node, safe, head){ INIT_LIST_HEAD(node); stack[i] = node; i++; } INIT_LIST_HEAD(head); for(i = 1; i < queue_size; i *= 2){ for(int j = 0; i + j < queue_size; j += (i * 2)){ stack[j] = merge_two_list(stack[j], stack[i + 1]); } } list_add_tail(head, stack[0]); ``` :::danger 不用列舉完整程式碼，HackMD 是讓你描述想法和過程中遇到的問題的地方，你應該只列出關鍵程式碼片段，並在之前就探討你的構思和對應的考量。 :notes: jserv ::: 這裡的 `q_merge_two` 的輸入參數不需要輸入 `head` 也就是沒有內存資料的部份。 另外，對於 `q_sort` 我的想法是，先透過尋訪整的佇列，並將所有節點堆疊在 `stack` 裡面，如此一來，只要在最後將所有節點兩兩合併，便可以得到結果。 #### `lib/list_sort.c` 研讀 此外，我研讀了 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 以及 [kdnvt](https://hackmd.io/@sysprog/linux2022-sample-lab0) 的整理。 1. `list_sort.c` 在 `merge` 和 `merge_final` 將串列當成單向鏈結串列，並無視 prev 指標的操作，最後再在 `merge_final` 時再串起來。 2. 在合併的過程中 `list_sort.c` 確保合併的兩個子串列的大小不會大於 $2:1$，如此一來便可以降低比較的次數，以增加 performance ： ```c /* * The number of pending lists of size 2^k is determined by the * state of bit k of "count" plus two extra pieces of information: * * - The state of bit k-1 (when k == 0, consider bit -1 always set), and * - Whether the higher-order bits are zero or non-zero (i.e. * is count >= 2^(k+1)). * * There are six states we distinguish. "x" represents some arbitrary * bits, and "y" represents some arbitrary non-zero bits: * 0: 00x: 0 pending of size 2^k; x pending of sizes < 2^k * 1: 01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k * 2: x10x: 0 pending of size 2^k; 2^k + x pending of sizes < 2^k * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k * 4: y00x: 1 pending of size 2^k; 2^k + x pending of sizes < 2^k * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k * (merge and loop back to state 2) */ ``` |count decimal|count binary|merge|before merge|after merge | -------- | -------- | -------- |---|---| 0|0000 |No| NULL| X 1|0001 |No| 1 |X 2|0010 |Yes| 1-1 |2 3|0011 |No| 1-2 |X 4|0100 |Yes| 1-1-2 |2-2 5|0101 |Yes| 1-2-2 |1-4 6|0110 |Yes| 1-1-4 |2-4 7|0111 |No| 1-2-4 |X 8|1000 |Yes| 1-1-2-4 |2-2-4 9|1001 |Yes| 1-2-2-4 |1-4-4 10|1010 |Yes | 1-1-4-4| 2-4-4 11|1011 |Yes | 1-2-4-4| 1-2-8 12|1100 |Yes| 1-1-2-8| 2-2-8 13|1101 |Yes | 1-2-2-8 |1-4-8 14|1110|Yes | 1-1-4-8 |2-4-8 15|1111 |No | 1-2-4-8 |X 16|10000 |Yes| 1-1-2-4-8| 2-2-4-8 #### 回頭檢查 `q_sort` 研讀完 `lib/list_sort.c` 後，我發現原本的程式碼有以下幾點做的不夠好 1. `int queue_size = q_size(head);` 我原本的程式碼使用 `q_size` 來獲得佇列的長度，以此來走訪所有節點，然而，這個做法式建立在「需要利用尋訪整個佇列，並把所有節點兩兩合併」的情況下才需要用到。若是參考 `lib/list_sort.c` 的做法，便不須要這樣做。 2. `stack` 在原本的程式碼中，我使用 `stack[STACKCAPACITY]` 來儲存佇列中所有節點，然而，這樣做會有 `stack` 的記憶體空間浪費或是不足的問題，因此這裡也改成 `lib/list_sort.c` 的 `pending` 的方法。 在考慮到這些因素後，我發現難以已 `lib/list_sort.c` 的作法來修改我的程式碼，並且我發現能夠使用 `lib/list_sort.c` 的想法來實做 `q_merge` 因此我打算先使用 `lib/list_sort.c` 的程式碼，並轉頭修改 `q_merge` 。 ### `q_descend` 我的想法為，利用 `curr_node` 和 `prev_node` 來尋訪整個佇列，如此一來便能夠直接透過比較來判斷是否移除。另外，這個函式必須使用相反的順序來尋訪，以確保迭代的過程中會不會遇到嚴格大於的節點。 ```c /* Remove every node which has a node with a strictly greater value anywhere to * the right side of it */ while (prev_node != head) { if (strcmp(list_entry(curr_node, element_t, list)->value, list_entry(prev_node, element_t, list)->value) < 0) { list_del(prev_node); q_release_element(list_entry(prev_node, element_t, list)); } curr_node = prev_node; prev_node = prev_node->prev; } ``` 不過，在實際測試後發現這個函式會有兩個問題： 1. 在刪除節點後 `curr_node` 應該保持不動。 2. 在 `prev_node` 被刪除後，便無法存取到 `prev_node->prev` 因此應該事先記錄下來 ```c while (prev_node != head) { if (strcmp(container_of(prev_node, element_t, list)->value, container_of(curr_node, element_t, list)->value) < 0) { tmp = prev_node->prev; list_del(prev_node); q_release_element(container_of(prev_node, element_t, list)); prev_node = tmp; } else { curr_node = prev_node; prev_node = prev_node->prev; } } ``` ### q_merge :::info 待補圖 待測試 待優化 ::: ```c= /* Merge all the queues into one sorted queue, which is in ascending order */ int q_merge(struct list_head *head) { if (!head || list_empty(head)) return 0; queue_contex_t *first_queue = container_of(head->next, queue_contex_t, chain); if (list_is_singular(head)) return first_queue->size; for (struct list_head *node = head->next->next; node != head; node = node->next) { queue_contex_t *target = container_of(node, queue_contex_t, chain); merge_two_queue(first_queue->q, target->q); if(first_queue->size + target->size < first_queue->size) return -1; first_queue->size += target->size; target->size = 0; } return first_queue->size; } ``` 這題參考了 [komark06](https://hackmd.io/@komark06/SyCUIEYpj#q_merge-%E5%AF%A6%E4%BD%9C) 的做法，並做出優化。 我在每次尋訪到新的佇列時就進行 `merge_two_list` 並更新 `first_queue->size` 而不是在最後才 `q_sort` 。 但是， `q_merge` 可以使用 divide-and-conquer 方法進行優化。 首先，透過走訪整個佇列，並將目前的節點和下一個節點合併 ```c if(queue != head && queue->next != head){ struct list_head *a_queue = queue, *b_queue = a_queue->next; queue_contex_t *a_queue_container= container_of(a_queue, queue_contex_t, chain), *b_queue_container = container_of(b_queue, queue_contex_t, chain); if(!a_queue_container->size){ list_del(a_queue); } if(!b_queue_container->size){ list_del(b_queue); } if(a_queue_container->size && b_queue_container->size){ if(a_queue_container->q->prev){ a_queue_container->q->prev->next = NULL; a_queue_container->q->prev = NULL; } if(b_queue_container->q->prev){ b_queue_container->q->prev->next = NULL; b_queue_container->q->prev = NULL; } a_queue_container->q->next = merge_two_queue(a_queue_container->q->next, b_queue_container->q->next); a_queue_container->size += b_queue_container->size; b_queue_container->size = 0; list_del(b_queue); } } ``` 結束迴圈的時間點就在只剩下一個佇列時。 不過，在我寫完這個函式後才發現，題目的要求是不能把 `queue_contex_t` 的節點移除掉的。因此須要再調整。 ## References [sysprog21/lab0-c: C Programming Lab - GitHub](https://github.com/sysprog21/lab0-c) [2023q1 Homework1 (lab0) contributed by < komark06 >](https://hackmd.io/@komark06/SyCUIEYpj#2023q1-Homework1-lab0) [linux/list_sort.c at master · torvalds/linux - GitHub](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) [2023q1 Homework1 (lab0) contributed by < kdnvt >](https://hackmd.io/@sysprog/linux2022-sample-lab0)
Last changed by  
 
roger61205
294

Read more

Approximaiton Algorithms

Given an input with its size n, we want out algorithms to

5/15/2024
Bucket Sort

Assume the input is generated by a random process that distributes elements uniformly over [0,1)

4/4/2024
Counting Sort

If the numbers, A[1..n], to be sorted are integers in \{0,1,...,k\}.

4/4/2024
Radix Sort

Radix SortSort least significant digits first.

4/4/2024
Read more from roger61205
Published on HackMD