--- tags: linux2022 --- # 2022q1 Homework1 (lab0) contributed by < [`ShawnLu31`](https://github.com/ShawnLu31) > ## 實驗環境 ```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: 39 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: GenuineIntel CPU family: 6 Model: 165 Model name: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz Stepping: 5 CPU MHz: 2900.000 CPU max MHz: 4800.0000 CPU min MHz: 800.0000 BogoMIPS: 5799.77 Virtualization: VT-x L1d cache: 256 KiB L1i cache: 256 KiB L2 cache: 2 MiB L3 cache: 16 MiB NUMA node0 CPU(s): 0-15 ``` ## 作業要求 > [lab0](https://hackmd.io/@sysprog/2020-lab0) - [x] 開發環境設定 - [x] Fork lab0 on github - [x] 佇列實作 - [x] `q_new`: 建立新的「空」佇列 - [x] `q_free`: 釋放佇列所佔用的記憶體 - [x] `q_insert_head`: 在 head 插入 (insert) 給定的新節點 (LIFO) - [x] `q_insert_tail`: 在 tail 插入 (insert) 給定的新節點 (FIFO) - [x] `q_remove_head`: 從 head 移去 (remove) 節點，回傳該節點 - [x] `q_remove_tail`: 從 tail 移去 (remove) 節點，回傳該節點 - [x] `q_release_element`: 釋放特定節點的記憶體空間 - [x] `q_size`: 計算目前佇列的節點總量 - [x] `q_delete_mid`: 移走佇列中間的節點 - [x] `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點 - [x] `q_swap`: 交換佇列中鄰近的節點 - [x] `q_reverse`: 以反向順序重新排列鏈結串列，不配置或釋放任何節點（重排已經存在的節點） - [x] `q_sort`: 以遞增順序來排序鏈結串列的節點 - [ ] 用 Graphviz 在 HackMD 筆記上視覺化展現 - [x] 引入 Git pre-commit hook - [x] 透過 clang-format 確保一致的程式風格 - [x] 詳閱 - [x] 使用 - [ ] 透過 GNU Aspell 進行拼字檢查 - [ ] 開啟 Cppcheck 靜態程式碼檢查功能 - [ ] 以 Valgrind 分析記憶體問題 ## 開發過程 ### 佇列架構 ### lish.h 巨集參考 - `INIT_LIST_HEAD()` - Initialize empty list head - Add new node - `list_add()` - Add a list node to the beginning of the list - `list_add_tail()` - Add a list node to the end of the list - `list_splice()` - Add list nodes from a list to beginning of another list - `list_splice_tail()` - Add list nodes from a list to end of another list - `list_splice_init()` - Move list nodes from a list to beginning of another list - `list_splice_tail_init()` - Move list nodes from a list to end of another list - Remove node - `list_del()` - Remove a list node from the list - `list_del_init()` - Remove a list node from the list and reinitialize it - Check - `list_empty()` - Check if list head has no nodes attached - `list_is_singular()` - Check if list head has exactly one node attached - Move - `list_cut_position()` - Move beginning of a list to another list - `list_move()` - Move a list node to the beginning of the list - `list_move_tail()` - Move a list node to the end of the list - Entry - `list_first_entry()` - get first entry of the list - `list_last_entry()` - get last entry of the list - iteraton - `list_for_each` - iterate over list nodes - `list_for_each_entry` - iterate over list entries ### 針對佇列的實作 #### `q_new` 用 `malloc` 取得 `struct list_head` 大小的記憶體。 - 如果失敗回傳 `NULL` 。 - 成功則用 `INIT_LIST_HEAD()` 做初始化。 ```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; } ``` :::danger 注意共筆書寫規範：中英文間用一個半形空白區隔 :notes: jserv ::: #### `q_free` 此函式須釋放佇列所有空間，所以須釋放 `element` 和 `l` 。 用 `list_for_each_entry_safe()` 走訪節點。 - entry ，對應 element 物件。 - safe ，允許移除目前節點。 用 `list_del()` 移出佇列， `q_release_element()` 釋放節點空間。 釋放佇列 `l` 。 ```c void q_free(struct list_head *l) { if (!l) return; /* queue is NULL */ element_t *del, *next; /* del, the element to be free. next, the next element of del */ list_for_each_entry_safe (del, next, l, list) { list_del(&del->list); q_release_element(del); } free(l); return; } ``` #### `q_insert_head` 若佇列是`NULL` 立刻回傳 false 。 用 `malloc` 取得 `element_t` 大小的記憶體。失敗回傳 false 。 用 `malloc` 取得 s 字串大小的記憶體。失敗釋放 e 的空間並回傳 false 。 用 `memcpy` 複製字串和 `INIT_LIST_HEAD()` 初始化新節點，再用 `list_add` 加入佇列最前端。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; /* queue is NULL */ element_t *e = malloc(sizeof(element_t)); if (!e) return NULL; /* could not allocate space */ int len = strlen(s) + 1; e->value = malloc(sizeof(char) * len); if (!e->value) { free(e); return NULL; /* could not allocate space */ } memcpy(e->value, s, len); INIT_LIST_HEAD(&e->list); list_add(&e->list, head); return true; } ``` ##### 更新： 用 `gen_element` 取代與 `q_insert_tail` 相同的程式。 ```c bool q_insert_head(struct list_head *head, char *s) { if (!head || !s) return false; /* queue is NULL or s is NULL*/ element_t *e = gen_element(s); if (!e) return false; list_add(&e->list, head); return true; } ``` #### `q_insert_tail` 大致與 `q_insert_head()` 相同。用 `list_add_tail()` 加入佇列尾端。 ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) return false; /* queue is NULL */ element_t *e = malloc(sizeof(element_t)); if (!e) return NULL; /* could not allocate space */ int len = strlen(s) + 1; e->value = malloc(sizeof(char) * len); if (!e->value) { free(e); return NULL; /* could not allocate space */ } memcpy(e->value, s, len); INIT_LIST_HEAD(&e->list); list_add_tail(&e->list, head); return true; } ``` ##### 更新： ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head || !s) return false; /* queue is NULL or s is NULL*/ element_t *e = gen_element(s); if (!e) return false; list_add_tail(&e->list, head); return true; } ``` ##### `gen_element` ```c element_t *gen_element(char *s) { element_t *e = malloc(sizeof(element_t)); if (!e) return NULL; /* could not allocate space */ int len = strlen(s) + 1; e->value = malloc(sizeof(char) * len); if (!e->value) { free(e); return NULL; /* could not allocate space */ } memcpy(e->value, s, len); INIT_LIST_HEAD(&e->list); return e; } ``` #### `q_remove_head` 若佇列為 `NULL` 或空，回傳 `NULL` 。 `list_first_entry()` 取得第一個節點位置， `list_del_init()` 移除該節點。 若 `sp` 不為 `NULL` ，複製節點的 `value` 到 `sp` 。 回傳該節點。 ```c 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_init(head->next); if (sp) memcpy(sp, e->value, strlen(e->value) + 1); return e; } ``` #### `q_remove_tail` 用 `q_remove_head()` 實作，傳入 `head->prev->prev` ，其取得的節點便是 `head->prev` 。 ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { return q_remove_head(head->prev->prev, sp, bufsize); } ``` #### `q_size` 一開始檢查佇列是否為 `NULL` 或空。 使用 `list_for_each()` 走訪佇列，計算節點數量，並回傳。 ```c int q_size(struct list_head *head) { if (!head || list_empty(head)) return 0; struct list_head *node; int count = 0; list_for_each (node, head) ++count; return count; } ``` #### `q_delete_mid` > 根據[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#circular-linked-list)中的範例實作 一開始檢查佇列是否為 `NULL` 或空。 使用快慢指標找到中間的節點。 - `indir` 指標一個迴圈走到下個節點（一個節點）， `fast` 指標一個迴圈走到下下個節點（兩個節點)。 - 當 `fast = head` (q_size is even) 或 `fast->next = head` (q_size is odd) 時，fast 已走 n 個節點， `*indir` 指向第 $n/2$ 節點，即為中間的節點 (0-based indexing)。 - 若 q_size = 6, `fast` 停在 5th 節點，`*indir` 指向 3th 節點 。 - 若 q_size = 5, `fast` 停在 3th 節點，`*indir` 指向 2th 節點 。 - `list_del()` 移除要刪除的節點，用 `list_entry()` 找到節點位置，再釋放空間。 ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **indir = &head->next, *fast = head->next; for (; fast != head && fast->next != head; fast = fast->next->next) indir = &(*indir)->next; struct list_head *del_node = *indir; list_del_init(del_node); element_t *del_e = list_entry(del_node, element_t, list); q_release_element(del_e); return true; } ``` #### `q_delete_dup` 若佇列為 `NULL` 回傳 `false` 。 用 `list_for_each_entry_safe()` ，因為它允許在走訪佇列時刪除節點。 - 若是 `str` 與 `node->value` 字串相同。移除 `node` 並釋放空間。否則將 `node->vale` 複製給 `str` ，成為下一個要比較的字串。 - 因為使用此函式的佇列須為已排序好的狀態，有相同字串的節點一定相鄰。一旦發現下個節點字串不同，目前節點的字串便不會再後續出現，不須再比較。 - 經由迴圈，會將 n 個有相同字串的節點的後 n-1 個節點刪除，因為第一次偵測到存在相同字串 `str` 時，同時至少有兩個節點，前一個是更新 `str` 時走訪，目前的節點是發現重複字串且將被刪除的節點，後續重複節點也被走訪後刪除。 為了刪除第一個節點，再刪除目前節點後檢查 `str` 和 `next->value`，若是**不同**，表示重複的 n-1 個節點已被刪除完畢，此時 `next` 的前一個節點就是重複的第一個節點（兩節點之前的其他節點都被移除），用 `list_entry()` 取得該節點 `first_dup` ，移除並釋放空間。 - 變數 - `str` 存目前比要對的字串。 - `node` 目前的節點，可被 delete 。 - `next` , `node` 的下一個節點。 - `first_dup` ， n 個有相同字串的節點中的第一個節點。 ```c bool q_delete_dup(struct list_head *head) { if (!head) return false; element_t *first_dup, *node, *next; char *str = malloc(sizeof(char) * 1024); list_for_each_entry_safe (node, next, head, list) { if (strcmp(str, node->value) == 0) { list_del_init(&node->list); q_release_element(node); if (strcmp(str, next->value) != 0) { /* delete the frist node that have duplicate string */ first_dup = list_entry(next->list.prev, element_t, list); list_del_init(&first_dup->list); q_release_element(first_dup); } } else { memcpy(str, node->value, strlen(node->value) + 1); } } free(str); return true; } ``` 改進： 將 `str` 指標指向目前比對的節點的 `value` ，取代原本的 `malloc` 和 `memcpy` ，減省記憶體空間。初始化則改為指向 `\0` 。 ```c bool q_delete_dup(struct list_head *head) { if (!head) return false; element_t *node, *next; char *str = "\0"; list_for_each_entry_safe (node, next, head, list) { if (strcmp(str, node->value) == 0) { ... if (strcmp(str, next->value) != 0) { /* delete the frist node that have duplicate string */ element_t *first_dup = list_entry(next->list.prev, element_t, list); list_del_init(&first_dup->list); q_release_element(first_dup); str = "\0"; } } else { str = node->value; } } return true; } ``` #### `q_swap` 若佇列為 `NULL` 、空，或只有一個節點，則回傳，不須 swap 。 根據 `list_for_each_safe` 迴圈，加上 `safe != head` 的條件，用來在節點為奇數時，剩下最後一個時停止迴圈。 交換節點位置： - `safe` 後移一個節點，原本 `safe` 的位置為 `node->next` ， 交換 `node` 和 `node->next` 兩節點。 - 更新連接 `node->prev` 和 `node->next` 。 - 更新連接 `node` 和 `node->next` 。 - 更新連接 `node` 和 `safe` 。 ```c void q_swap(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; struct list_head *node, *safe; for (node = head->next, safe = node->next; node != head && safe != head; node = safe, safe = node->next) { safe = safe->next; node->prev->next = node->next; node->next->prev = node->prev; node->prev = node->next; node->next->next = node; safe->prev = node; node->next = safe; } } ``` #### `q_reverse` 確認佇列是否為 `NULL` 或空。 用 `list_for_each_safe` 走訪節點，交換 `node` 的兩個指標 `node->prev` `node-。next` 指向的位址。因為 `list_for_each_safe` 是從第一個節點開始，迴圈結束後交換 `head` 的兩個指標 `prev` `next` 指向的位址（此時 `node == head`）。 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) return; struct list_head *node, *next; list_for_each_safe(node, next, head) { node->next = node->prev; node->prev = next; } node->next = node->prev; node->prev = next; return; } ``` #### `q_sort` 若佇列為 `NULL` 、空或只有一個節點，則不做排序。 根據 Quick sort 實作排序，將傳入的第一個節點 `head` 當作比較的基準值，數值小的節點移動到 `head` 前，數值相同或大於則維持原位。再用遞迴繼續排序 `head` 的左右子佇列。 用 `prev` 和 `next` 兩個指標的指標操作。 - 立即回傳，不做迴圈 - `tail->next == head` 表示上一層遞迴後左子佇列或右佇列為空。 - `head == tail` 表示上一層遞迴後左子佇列或右佇列只有移的節點。 - 迴圈 - 初始 `prev` `next` 都指向 `head` 。 - 若 `*next->next` `value` 小於 `head` `value` ，移到 `*prev` 節點的前面，然後 `prev` 指標指向該節點。 - 否則（`*next->next` `value` 大於等於 `head` `value`）， `next` 指向下一個節點。 - 若 `*next == tail` （`*prev == tail`） 表示此子佇列已比較完所有節點且最後一個節點大於等於（小於）`head` 。 - 遞迴呼叫 - `prev` 和 `next` 再比較後都會指向比較後的節點，因此分別作為左子佇列的 `head` 和右子佇列 `tail` 。 ```c void sort(struct list_head *head, struct list_head *tail) { if (tail->next == head || head == tail) return; struct list_head **prev = &head, **next = &head; char *head_str = list_entry(head, element_t, list)->value; for (; (*next) != tail && (*prev) != tail;) { char *str = list_entry((*next)->next, element_t, list)->value; if (strcmp(str, head_str) < 0) { (*prev)->prev->next = (*next)->next; (*next)->next->prev = (*prev)->prev; (*prev)->prev = (*next)->next; (*next)->next = (*next)->next->next; (*next)->next->prev = *next; (*prev)->prev->next = *prev; prev = &(*prev)->prev; } else { next = &(*next)->next; } } sort(*prev, head->prev); sort(head->next, *next); return; } void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) return; sort(head->next, head->prev); } ``` ## 參考資訊 - 共筆格式參考：[共筆示範](https://hackmd.io/@cccccs100203/linux2020-lab0)
Last changed by  
 
翔
325

Read more

2022q1 Homework1 (quiz1)

contributed by < ShawnLu31 > 題目 測驗 1 解題 map_add 分配一個節點空間，並將此節點放入 hash table 。 宣告完 h n 後： first 指向該 hash table 的欄位的必一個節點，可能是 NULL，因此用 if 確認節點的的存在。

6/23/2022
2022q1 Homework2 (quiz2)

contributed by < ShawnLu31 > 測驗 1 解釋程式碼 uint32_t average(uint32_t a, uint32_t b) { return (a + b) / 2; } 簡單地將 a 和 b 相加後除以 2 。但此作法可能導致 overflow，例如： uint32 的最大值相加。

4/24/2022
Read more from 翔
Published on HackMD