2022q1 Homework1 (lab0)

# 2022q1 Homework1 (lab0) contributed by < `tseng0201` > :::danger 在「作業區」以「[固定網址](https://hackmd.io/s/how-to-share-note-tw)」填寫 HackMD 超連結，請注意細節！ :notes: jserv ::: ## 前置作業: - [x] 閱讀 [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer) - [X] 閱讀 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) - [X] 詳閱 [lab0](https://hackmd.io/@sysprog/linux2022-lab0) 作業需求 ## queue.c實現進度: - [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: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked List - [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List II - [x] q_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairs - [X] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點; - [x] q_sort: 以遞增順序來排序鏈結串列的節; ## 更多 - [ ] 了解lab0中提到的分析工具 Cppcheck Valgrind Perf - [x] 在 qtest 提供新的命令 shuffle - [ ] 在 qtest 提供新的命令 web - [ ] 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。 - [ ] 研讀論文〈Dude, is my code constant time?〉，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理。注意：現有實作存在若干致命缺陷，請討論並提出解決方案; - [ ] 指出現有程式的缺陷 (提示: 和 RIO 套件有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request ## 實驗環境: ```shell 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): 8 On-line CPU(s) list: 0-7 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 94 Model name: Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz Stepping: 3 CPU MHz: 816.656 CPU max MHz: 4000.0000 CPU min MHz: 800.0000 BogoMIPS: 6799.81 Virtualization: VT-x L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 8 MiB NUMA node0 CPU(s): 0-7 ``` ## queue.c實現: 想法：利用 linux 已經實現的 `struct list_head` 與其相關巨集/函式進行 queue 節點間的移動,再透過 container_of / list_entry 取得其他該節點的成員進行操作 ### 自定義struct #### q_head 在原有的head定義下新增 count 用於計算queue的長度, count 為0時代表一個空的 queue ```c typedef struct { int count; struct list_head group; } q_head; ``` ### 定義queue節點 #### queue_member 已定義於queuq.h 藉由定義好的 struct list_head 進行節點間的移動, 以成員 value(pointer to char）紀錄該節點的資料 ```c * Linked list element */ typedef struct { /* Pointer to array holding string. * This array needs to be explicitly allocated and freed */ char *value; struct list_head list; } element_t; ``` ### 自定義函式 q_delete_element() delete 一個 queue member 先移出 queue 再釋放其記憶體位置 ```c void q_delete_element(struct list_head *node) { if (!node) { return; } list_del(node); free(list_entry(node, element_t, list)->value); free(list_entry(node, element_t, list)); } ``` #### void list_swap() 交換兩個 list_head* 所指向的位置 ```c void list_swap(struct list_head **list_addr1 ,struct list_head **list_addr2 ) { struct list_head *temp = *list_addr2; *list_addr2 = *list_addr1; *list_addr1 = temp; } ``` ### 實現的函式 #### q_new() 建立一個空的queue head，並將 count 設為0 並透過 INIT_LIST_HEAD() 將 prev, next指標都指向自己當 memory allocate 失敗將會返回 NULL 新增當 allocate 失敗時回傳 NULL 不再進行後續操作 ```c struct list_head *q_new() { q_head *temp = malloc(sizeof(q_head)); if (!temp) { return NULL; } temp->count = 0; INIT_LIST_HEAD(&temp->list); return &temp->list; } ``` #### q_free() 將整個 queue 包含 queue head 所佔用的記憶體釋放,由於 queue 的資料是由 pointer 紀錄,所以要先釋放掉其指向的記憶體,再釋放掉節點本身函式透過 temp 紀錄要消除的節點, 並修改 queue head 的 next 紀錄下一個要消去的節點, 最後才將queue head 釋放 ```c void q_free(struct list_head *l) { if (!l) { return; } struct list_head *temp = l->next; while (l != temp) { l->next = temp->next; free(list_entry(temp, element_t, list)->value); free(list_entry(temp, element_t, list)); temp = l->next; } free(list_entry(l, q_head, list)); return; } ``` #### q_insert_head 建立一個新的節點插入在 head next, 由於字串是由 pointer傳入無法使用 sizeof 取得字串長度所以直接使用 for loop 計算長度後再分配適當的空間建立新的節點後使用 list_add 自動將其指標指向正確位置使用strlcpy 而非 strncpy 兩者都可以防止輸入大於分配的空間,但strlcpy還會將最後一個改為 '\0' 用起來更安全新增當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free) ```c bool q_insert_head(struct list_head *head, char *s) { if (!head) { return false; } element_t *temp_member = malloc(sizeof(element_t)); if (!temp_member) { return false; } int count = 0; for (; s[count]; count++) { }; temp_member->value = malloc(count + 1 * sizeof(char)); //check successful malloc if (!temp_member->value ) { free(temp_member); return false; } strlcpy(temp_member->value, s, count + 1); list_add(&temp_member->list, head); list_entry(head, q_head, list)->count += 1; return true; } ``` #### q_insert_tail 同 q_insert_head ,但指標操作改為list_add_tail 新增當 data malloc 失敗時函式回傳 false,且要將剛建立的 element_t 物件釋放 (free) ```c bool q_insert_tail(struct list_head *head, char *s) { if (!head) { return false; } element_t *temp_member = malloc(sizeof(element_t)); if (!temp_member) { return false; } int count = 0; for (; s[count]; count++) { }; temp_member->value = malloc(count + 1 * sizeof(char)); if (!temp_member->value ) { free(temp_member); return false; } strlcpy(temp_member->value, s, count + 1); list_add_tail(&temp_member->list, head); list_entry(head, q_head, list)->count += 1; return true; } ``` #### q_size 回傳 queue 的長度, 直接回傳 q_head 的 count 即可 ```c int q_size(struct list_head *head) { if (!head) { return 0; } return list_entry(head, q_head, group)->count; } ``` #### q_remove_head 將第一個 queue 節點從 queue 中斷開, 並將其 value 轉移至 sp 當 head 為 NULL 或 empty 時回傳 NULL 使用strlcpy 進行字串複製這樣會自動在最後加上 '\0' 並使用list_del進行 queue之間的修改 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)){ return NULL; } element_t *temp = list_entry(head->next, element_t, list); list_del(head->next); if (sp) { strlcpy(sp, temp->value, bufsize); } list_entry(head, q_head, list)->count -= 1; return temp; } ``` #### q_remove_tail 刪除queue中最後的節點 ,概念q_remove_head ```c element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head || list_empty(head)){ return NULL; } element_t *temp = list_entry(head->prev, element_t, list); list_del(head->prev); if (sp) { strlcpy(sp, temp->value, bufsize); } list_entry(head, q_head, list)->count -= 1; return temp; } ``` #### q_size 回傳 queue 的長度, 直接回傳 q_head 的 count 即可 ```c int q_size(struct list_head *head) { if (!head) { return 0; } return list_entry(head, q_head, group)->count; } ``` #### q_delete_mid 移除queue中間的節點, 透過 queue head 的 count 即可快速求出該中間節點,透過ptr移動至該節點後先移出(remove) queue 再進行刪除(delete) count 要減1 待改進的點 : head 其實算完 count 後不需要了可以直接拿來當ptr ```c bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) { return false; } int n = list_entry(head, q_head, list)->count-- / 2; // list_entry(head, q_head, list)->count -= 1; struct list_head *ptr = head->next; while (n--) { ptr = ptr->next; } q_delete_element(ptr); return true; } ``` #### q_delete_dup 把重複的節點都刪除 e.g. old: 1->2->2->3 改為 1->3 注意：此程式必須為排序過的 list 才適用設定 ptr 為當前節點的節點並與 ptr->next 比較,如果相同則刪除ptr->next 否則該節點保留 kill_self 用來紀錄當前 ptr 是否為duplicate的一部分如果kill_self 為 true 則節點也應該刪除 ```c bool q_delete_dup(struct list_head *head) { if (!head) { return false; } if (list_empty(head) || list_is_singular(head)) { return true; } int count = list_entry(head, q_head, list)->count; struct list_head * ptr = head->next; bool kill_self = false; while (ptr != head && ptr->next != head) { while (ptr->next != head && !strcmp(list_entry(ptr, element_t, list)->value, list_entry(ptr->next, element_t, list)->value)) { q_delete_element(ptr->next); count--; kill_self = true; } ptr = ptr->next; if (kill_self) { q_delete_element(ptr->prev); kill_self = false; count--; } } list_entry(head, q_head, list)->count = count; return true; } ``` #### q_swap() 將 queue 中的節點每兩個兩個相反,且不能改變node value e.g. a->b->c->d 改為b->a->d->c 此程式以單向 link_list 方向思考,最後再以 while 迴圈將prev 指向正確的節點 ptr 紀錄當前節點 first second 紀錄當前節點的下個與下下個代表要交換的兩個節點 ```c void q_swap(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) { return; } struct list_head * ptr = head; while (ptr->next != head && ptr->next->next != head) { struct list_head * first = ptr->next; struct list_head * second = ptr->next->next; first->next = second->next; ptr->next = second; ptr->next->next = first; ptr = ptr->next->next; } ptr = head; while (ptr->next != head) { ptr->next->prev = ptr; ptr = ptr->next; } head->prev = ptr; return ; } ``` #### q_reverse 由於 queue是雙向的環所以只要將每個節點(包含 head)的 prev 與 next 指向的位置換就好 ```c void q_reverse(struct list_head *head) { if (!head || list_empty(head)) { return; } struct list_head *temp = head; do { struct list_head *t = temp->next; temp->next = temp->prev; temp->prev = t; temp = temp->prev; } while (temp != head); } ``` #### q_sort 以三個函式實現 1.q_sort : 呼叫界面 2.list_mergesort() : 執行mergesort 3.merge_two_list : 執行merge ##### merge_two_list() 引用：[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists)中的實做進行概念是讓一個指標 ptr 每次都走向 q_1 或 q_2 value 比較小的節點,然後移動被選中的節點至其下一個,當ptr走完兩個 list 便可得到一個依 value 由小到大串在一起的list 程式碼解析在引用的實做中, 使用** 進行對指標的紀錄與移動 1.ptrㄧ開始指向節點本身而之後都是指向節點的 next 2.node 為紀錄目前比較小的那個節點並進行操作 ```c *node = (*node)->next ``` 上列函式可看做 ```c if(l1 < l2) l1 = l1->next; else l1 = l1->next; ``` 3.透過 node 紀錄當前較小的節點並透過 ptr 串起走訪的節點 ```c struct list_head** ptr ; *ptr = *node; 可以看作 struct list_head* ptr; ptr->next = (q_1 < q_2) ? q_1 : q_2 ``` 4.地址的 bitwise操作 c 不允對指標指向的地址做 or 所以將地址強制轉形成 unsigned int 進行操作後再轉回本的型態 C99規格書上面寫道 >6.5.12 BitwiseinclusiveORoperator >Constraints: >Each of the operands shall have integer type. ```c (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2); ``` 以下為完整程式碼 ```c struct list_head* merge_two_list(struct list_head *q_1,struct list_head *q_2) { if (!q_1 || !q_2) return (struct list_head *) ((__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2); struct list_head *head = NULL, **ptr = &head, **node; for (node = NULL; q_1 && q_2; *node = (*node)->next) { node = (strcmp(list_entry(q_1, element_t, list)->value, list_entry(q_2, element_t, list)->value) <= 0 ) ? &q_1: &q_2; *ptr = *node; ptr = &(*ptr)->next; } *ptr = (struct list_head *)( (__UINTPTR_TYPE__) q_1 | (__UINTPTR_TYPE__) q_2 ); return head; } ``` ##### merge_two_list() 利用 divine and counquer 的概念進行分割與合併,將原本 queue 分隔為多個長度為1的 queue 後再進行合併,分割使用slow、fast 指標取的中間的節點、並分為left 與 right 處理最後回傳merge後的queue ```c struct list_head* list_mergesort(struct list_head * head) { if (!head || !head->next) { return head; } struct list_head *slow = head; struct list_head *fast = head->next; for (; fast && fast->next; fast = fast->next->next) { slow = slow->next; } fast = slow->next; slow->next = NULL; struct list_head * left = list_mergesort(head); struct list_head * right = list_mergesort(fast); return merge_two_list(left, right); } ``` ##### q_sort() 首先先將環狀的queue 斷開成直線的queue ```c head->prev->next = NULL; ``` 再將queue進行sort ```c head->next = list_mergesort(head->next); ``` 最後透過迴圈將 prev 修正並修復回環狀的queue ```c struct list_head *ptr = head; while (ptr->next) { ptr->next->prev = ptr; ptr = ptr->next; } ptr->next = head; head->prev = ptr; ptr = head; ``` 以下為完整程式碼 ```c void q_sort(struct list_head *head) { if (!head || list_empty(head) || list_is_singular(head)) { return; } head->prev->next = NULL; head->next = list_mergesort(head->next); struct list_head *ptr = head; while (ptr->next) { ptr->next->prev = ptr; ptr = ptr->next; } ptr->next = head; head->prev = ptr; ptr = head; return; } ``` ### 更多 #### 在 qtest 提供新的命令 shuffle ##### shuffle實現使用 Fisher–Yates shuffle 演算法,每次隨機選擇一個節點與最後一個尚未交換過的節點交換其 value (不改變節點順序) ```c void q_shuffle(struct list_head *head) { //檢查head 是否需要進行shuffle if (!head || list_empty(head) || list_is_singular(head)) { return; } //取的目前的節點數 int count = list_entry(head, q_head, list)->count; //紀錄最後一個尚未交換過的節點 struct list_head *last = head->prev; //不斷的進行隨機的交換 for (; count >1; count--) { int need_change = rand()%count; struct list_head *ptr = head->next; //移動指標至被選到的節點 for(; need_change > 0; need_change--) { ptr = ptr->next; } //交換被選到的節點與最後的節點 char *temp = list_entry(last, element_t, list)->value; list_entry(last, element_t, list)->value = list_entry(ptr, element_t, list)->value; list_entry(ptr, element_t, list)->value = temp; last = last->prev; } return; } ``` ##### 修改qtest 根據 lab0 的引導在 console_init()新增指令shuffle, 並實現 do_shuffle 函式進行 q_shuffle 此函式參考 do_swap() 實現 ```c static bool do_shuffle(int argc, char *argv[]) { //檢查時否有輸入其他參數 if (argc != 1) { report(1, "%s takes no arguments", argv[0]); return false; } //檢查queue是否已建立 if (!l_meta.l) report(3, "Warning: Try to access null queue"); error_check(); set_noallocate_mode(true); if (exception_setup(true)) q_shuffle(l_meta.l); exception_cancel(); set_noallocate_mode(false); show_queue(3); return !error_check(); } ```

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.