2020q1 Homework1 (lab0)

# 2020q1 Homework1 (lab0) contributed by < `gpwork4u` > ## 實驗環境 ```shell $ uname -a Linux 5.3.0-28-generic #30~18.04.1-Ubuntu SMP Fri Jan 17 06:14:09 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux $ gcc --version gcc (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0 ``` ## 作業要求 - 詳細閱讀 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ，依據指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，記得也該實作 `q_sort` 函式 - 修改排序所用的比較函式，變更為 `natural sort`，在 “simulation” 也該做對應的修改，得以反映出 `natural sort` 的使用。 - 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗 - 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理; - 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 :arrow_forward: 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository) ## 開發過程 ### queue.h ```cpp typedef struct { list_ele_t *head, *tail; int size; } queue_t; ``` 根據老師提供的作業說明所作的修改，加上一個 int size 變數在每次增減元素時做紀錄。在實作```q_insert_tail```時，要求要將原本 $O(n)$ 的時間修改為 $O(1)$ ，因此在 ```queue_t``` 中增加一個 ```tail``` 指標，以便直接在 queue 的尾端新增元素。參考 [OscarShiang ](https://hackmd.io/@WaryvM_MTuOkXtEEalFsvQ/Sy5oUP6MU#%E5%AF%A6%E4%BD%9C-q_reverse) 同學指標的使用方法，改用 `list_ele_t *tmp` 指標進行操作。 ### queue.c #### q_new - 回傳一個空的 queue - 當 malloc 失敗時需要回傳 NULL ```c queue_t q_new() { queue_t *q = malloc(sizeof(queue_t)); if (!q) return NULL; q->head = NULL; q->tail = NULL; q->size = 0; return q; } ``` #### q_size - return queue 的元素數量 - queue 為 NULL 時 return 0; ```c int q_size(queue_t *q) { if (!q) return 0; return q->size; } ``` 把 ```q->size``` 直接傳回去就是一開始實作的時候沒考慮 queue 為 NULL 的情形，加進去之後分數會多六分 #### q_free - 將 queue 中佔用的記憶體釋放 - 當 queue 為 NULL 時，直接 return 結束 ```c void q_free(queue_t *q) { if (!q) return; while (q->head) { list_ele_t *tmp; q->head = q->head->next; free(tmp->value); free(tmp); } free(q); } ``` 從 head 依序拜訪各個元素並作釋放最後再將 queue 的指標釋放 #### q_insert_head - 從 queue 的 head 插入一個元素 - 當 queue 為 NULL 或分配位置時失敗 return false ```c bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; if (!q) return false; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(sizeof(char)*(strlen(s) + 1)) if (!newh->value) { free(newh); return false; } snprintf(newh->value, strlen(s) + 1, "%s", s); newh->next = q->head; q->head = newh; if (!q->tail) q->tail = newh; q->size++; return true; } ``` 在 queue 為空時需要另外將 tail 也指向新增的元素於作業說明中提到 >依據 [CERN Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 gets / sprintf / strcpy 等不安全的函式; 因此在將資料傳給 newh->value 時為了避免使用 strcpy ，改採用根據 CERN 所提供的建議中的snprintf函式來進行操作。 >**int snprintf(char * restrict s, size_t n, const char * restrict format, ...);** 在使用snprintf時，將參數 ```size_t n``` 設為 ```strlen(s)```時，會發現輸出結果跟預期的不一樣，如下 ``` shell cmd> new q = [] cmd> ih 123 cmd> ih 123 q = [12] ``` 在經查閱[C99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)之後，其對於 snprintf的敘述如下 > The snprintf function is equivalent to fprintf, except that the output is written into an array (specified by argument s) rather than to a stream. If n is zero, nothing is written, and s may be a null pointer. Otherwise, output characters beyond the n-1st are discarded rather than being written to the array, and a null character is written at the end of the characters actually written into the array. If copying takes place between objects that overlap, the behavior is undefined. 從中可以知道， ```snprintf``` 會根據 ```size_t n``` ，將第 n-1 個位置以後的字串捨棄，並在第 n 位放入 NULL，因此在利用 strlen(s) 作為 Buffer size 時，須加一才能將完整的 s 值傳進 ```newh->value``` 。在 value 做 malloc 的時候，一開始是使用 ```sizeof(s)``` 配置記憶體空間，後來在後續的測試中發現傳入的字串大小大於等於 8 時，在進行釋放的時候會出現。 > ERROR: Corruption detected in block with address 0x558b91c49ce0 when attempting to free it 後來測試的時候發現 ```malloc(sizeof(s))``` 並不會配置一個跟 ```s``` 一樣的記憶體大小，而是 pointer 大小，導致在只用 ```sizeof(s)``` 作分配時不夠大，在用```snprintf``` 放入字串過大導致在釋放記憶體時動到了原本沒分配的部份，最後改用 ```sizeof(char)*strlen(s)+1``` 就可解掉這個 error，在 ```q_insert_tail``` 更新了一樣的作法。根據 C 規格書中對 sizeof 的描述，如傳入的 sizeof(s) 中 s 是個陣列的話，是可以直接用的，當是 pointer 時就只會是 pointer 的大小，而在 64 位元的系統中，一個 pointer 的大小即是8個 byte 。 > When sizeof is applied to an operand that has type char, unsigned char, or signed char, (or a qualified version thereof) the result is 1. When applied to an operand that has array type, the result is the total number of bytes in the array. >103) When applied to an operand that has structure or union type, the result is the total number of bytes in such an object, including internal and trailing padding. #### q_insert_tail - 從 queue 的尾端新增一個元素 - 成功return true - 若 queue 為 NULL 或分配位置失敗時則 return false - 時間複雜度須為 $O(1)$ ，即不論 queue 的長度為何執行時間，操作步驟為固定數量。 ```c bool q_insert_tail(queue_t *q, char *s) { list_ele_t *newh; if (!q) return false; newh = malloc(sizeof(list_ele_t)); if (!newh) return false; newh->value = malloc(sizeof(char)*(strlen(s) + 1)) free(newh); return false; } snprintf(newh->value, strlen(s) + 1, "%s", s); newh->next = NULL; q->size++; if (!q->tail) { q->head = newh; q->tail = newh; return true; } q->tail->next = newh; q->tail = newh; return true; } ``` 在 queue 為空時需要另外將 head 也指向新增的元素 #### q_remove_head - 將 queue head 刪除 - 成功刪除 return true - 當 queue 為空或 NULL 時 return false - 若 ```sp``` 不是 NULL 且 remove 執行成功時要將被 remove 的元素值的前bufsize - 1 位放進 ```sp``` 中，並且 sp 的最後一位須為 null terminator。 ```cpp bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if(!q || !q->head) return false; list_ele_t *tmp; tmp = q->head; if (sp) { snprintf(sp, bufsize, "%s", tmp->value); } q->head = q->head->next; free(tmp->value); free(tmp); q->size--; return true; } ``` 在將被 remove 值放進 sp 中，要求要取被 remove 的元素值前 bufsize - 1 位，在 insert 時用到的 ```snprintf```，剛好就可以拿來使用。 #### q_reverse - 將 queue 的內容反轉 - queue 為 NULL 或 empty 時直接結束 - 不能 allocate 新的記憶體位址和 free 原有的記憶體位址 ``` c void q_reverse(queue_t *q) { if (!q) return; if (q->size <= 1) return; list_ele_t *tmp; q->tail->next = q->head; while (q->head->next != q->tail) { tmp = q->head->next; q->head->next = tmp->next; tmp->next = q->tail->next; q->tail->next = tmp; } q->tail = q->head; q->head = q->head->next; q->tail->next = NULL; } ``` 除了 queue 為 NULL 和 empty 時，```q->size``` 為 1 時也可以直接結束。一開始的想法是用拆一個接一個的方式從 ```q->head``` 依序將元素拆掉並重新反向接上，在接完之後需要另外將 ```q->tail``` 歸位。後來想到先把 ```q->tail``` 接到 ```q->head``` 上，並依序將 ```q->head``` 到 ```q->tail``` 之間的元素接到 ```q->tail``` 後面，最後只須將```q-tail``` 和 ```q->head``` 互換位置，再將```q->tail->next``` 接到 NULL 即可，示意圖如下。 ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> a | <ref> }", width=1.2] b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; a:ref:c -> b:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> a :data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head [shape=box]; head -> a; tail [shape=box]; tail -> c; } ``` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> a | <ref> }", width=1.2] b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; a:ref:c -> c:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b :data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head [shape=box]; head -> a; tail [shape=box]; tail -> c; } ``` ```graphviz digraph linked_list{ rankdir=LR; node [shape=record]; a [label="{ <data> a | <ref> }", width=1.2] b [label="{ <data> b | <ref> }"]; c [label="{ <data> c | <ref> }"]; a:ref:c -> NULL [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false, arrowsize=1.2]; b:ref:c -> a:data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; c:ref:c -> b :data [arrowhead=vee, arrowtail=dot, dir=both, tailclip=false]; head [shape=box]; head -> c; tail [shape=box]; tail -> a; } ``` #### q_sort - 將 queue 中元素小到大做排序 - 使用 natual sort (未完成) ``` cpp void q_sort(queue_t *q) { if (!q) return; if (q->size <= 1) return; merge_sort(&(q->head)); while (q->tail->next) q->tail = q->tail->next; } ``` ##### sort.c ``` cpp #include <stdio.h> #include <string.h> #include "queue.h" void split(list_ele_t *source, list_ele_t **pre_head, list_ele_t **post_head) { list_ele_t *fast, *slow; fast = source->next; slow = source; while (fast) { fast = fast->next; if (fast) { fast = fast->next; slow = slow->next; } } *pre_head = source; *post_head = slow->next; slow->next = NULL; } list_ele_t *merge(list_ele_t *pre_head, list_ele_t *post_head) { list_ele_t *start, *current; start = pre_head; pre_head = pre_head->next; current = start; while (pre_head && post_head) { if (strcmp(pre_head->value, post_head->value) > 0) { current->next = post_head; post_head = post_head->next; } else { current->next = pre_head; pre_head = pre_head->next; } current = current->next; } if (pre_head) current->next = pre_head; else if (post_head) current->next = post_head; return start; } void merge_sort(list_ele_t **head) { list_ele_t *pre_head, *post_head; if (!(*head)) return; if (!(*head)->next) return; split(*head, &pre_head, &post_head); merge_sort(&pre_head); merge_sort(&post_head); if (strcmp(pre_head->value, post_head->value) <= 0) { *head = merge(pre_head, post_head); } else { *head = merge(post_head, pre_head); } } ``` 採用 merge sort 進行排序，即使在 worst case，merge sort 也是 $O(nlog{n})$ 的時間複雜度。實作的部份參考 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) :::danger TODO: 1. 在 `merge` 和 `merge_sort` 這二個函式都呼叫到 `strcmp`，也就是 comparator，倘若想更換後者為其他函式 (或傳遞函式指標)，那就需要在這兩個函式內容變更，不僅不便利，還會隱藏風險; 2. `split` 函式通用性不足，可改為巨集或 inline function 實作; 3. 考慮到 `merge_sort` 函式原型宣告的變更: ```cpp static list_ele_t *merge_sort(list_ele_t *head); ``` 輸入原本的 head，回傳因為排序而得到新的 head，在實作和使用上都會更便利; :notes: jserv ::: ## 參考資料 * [2020 春季 lab0c 作業說明](https://hackmd.io/@sysprog/linux2020-lab0) * [C Programming Lab: Assessing Your C Programming Skills](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) * [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) * [C11 規格書](https://web.cs.dal.ca/~vlado/pl/C_Standard_2011-n1570.pdf) * [Drawing Graphs using Dot and Graphviz](http://www.tonyballantyne.com/graphs.html)

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.