# 2020q3 Homework1 (lab0)
contributed by < `tungtylee` >
###### tags: `homework`
###### 為網路參與課程的學員 (非修課/非旁聽)
## Outline
[TOC]
## 開發環境
```
$ uname -a
Linux hwm 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
```
## 作業需求
### 完成
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:已
* [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_size`: 計算佇列中的元素數量。
* [x] `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* [x] ==`q_sort`==: 「[進階電腦系統理論與實作](http://wiki.csie.ncku.edu.tw/sysprog/schedule)」課程所新增，以==遞增順序==來排序鏈結串列的元素，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
### 未完成
1. [ ] 探索 [GNU/Linux 開發環境](https://hackmd.io/@sysprog/gnu-linux-dev)並善用 [Git](https://git-scm.com/) 進行版本控制
* 整合 [Valgrind](https://valgrind.org/) 動態程式分析工具，作為精準的記憶體分析和除錯
3. [ ] 除了原本對佇列的插入、刪除、反轉等操作外，額外要求針對佇列和鏈結串列撰寫排序程式，並思考高效能的實作;
* 原本作業註解提示 `It should operate in O(1) time` 卻未有自動評分，本課程參照 [dudect](https://github.com/oreparaz/dudect) 工具及對應的論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，提出以實驗而非理論驗證時間複雜度的方法
5. [ ] 支援 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，強化執行時期的記憶體檢測;
### q_new
* Check returned value of `malloc`:
一開始的 `q_new` 十分單純只是需要判斷 `malloc` 是否失敗。但隨著後面功能的新增，介面新增了 `tail` 以及 `size`，因此須新增改兩個變數的初始化。（第八行及第九行）
```c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
/* ANS: Make the queue NULL */
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
} else {
q = NULL;
}
return q;
}
```
### q_free
* Free `queue_t`, `list_ele_t`, and string in `list_ele_t`:
由於有三種結構會需要使用動態配置記憶體，因此在釋放記憶體需要三種結構都進行，我採用 linked list 上從頭走訪並釋放，釋放 `list_ele_t` 中的字串優先，但接著要刪除自己本身時，會遺失下一個連結位置，因此我們我們先暫存位置至 `past_ele_ptr` ，先移動至下一個連結位置再將前一個元素釋放掉。
```c=
/* Free all storage used by queue */
void q_free(queue_t *q)
{
/* TODO: How about freeing the list elements and the strings? */
/* Free queue structure */
/* It consists queue_t, list_ele_t, and string in list_ele_t */
list_ele_t *curr_ele_ptr;
if (q) {
curr_ele_ptr = q->head;
} else
curr_ele_ptr = NULL;
while (curr_ele_ptr) {
list_ele_t *past_ele_ptr = curr_ele_ptr;
free(curr_ele_ptr->value);
curr_ele_ptr = curr_ele_ptr->next;
free(past_ele_ptr);
}
free(q);
}
```
### q_insert_head
* `strncpy`, `strlen` 字串處理函數的使用:
在 `q_insert_head` 中最要小心的部份就是 C 語言的字串拷貝，在這邊我先用 `strlen` 算出字串長度，並加上 `\0` 的字串結尾，配置完記憶體再採用 `strncpy` ，此版本提供了上限，較 `strcpy` 安全。但實際上比較讓人擔心的問題是，當作輸入的 `char* s` 是否為一個正確的字串，有無正確使用 `\0` 在字串尾端。本版本還需要對無法正確配置字串進行處理，若無法配置則須釋放已配置記憶體。
```c=
bool q_insert_head(queue_t *q, char *s)
{
+ if (!q)
+ return false;
+
list_ele_t *newh;
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
+
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
- newh->next = q->head;
- q->head = newh;
- return true;
+ if (newh) {
+ size_t len = strlen(s) + 1;
+ newh->value = malloc(sizeof(char) * len);
+ if (newh->value) {
+ strncpy(newh->value, s, len);
+ } else {
+ free(newh);
+ return false;
+ }
+ // Update q when all data are ready
+ newh->next = q->head;
+ q->head = newh;
+ return true;
+ } else
+ return false;
}
```
### q_insert_tail
* 介面修改：
作業內提到需要能夠 `O(1)` 複雜度，因此不進一步修改 queue 介面無法達成。
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t size;
} queue_t;
```
* `q_create_elem`:
由於 `q_insert_head` 與 `q_insert_tail` 有部份程式碼相同，因此我抽象化出 `q_create_elem` ，但是有兩個東西需要回傳包含創建是否成功及新產生的 `list_ele_t` 位置。因此我採用了一個參數 `list_ele_t **newelem` 來得到配置的位址。
```c=
bool q_create_elem(queue_t *q, char *s, list_ele_t **newelem)
{
if (!q)
return false;
/* TODO: What should you do if the q is NULL? */
*newelem = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (*newelem) {
size_t len = strlen(s) + 1;
(*newelem)->value = malloc(sizeof(char) * len);
if ((*newelem)->value) {
strncpy((*newelem)->value, s, len);
} else {
free(*newelem);
return false;
}
return true;
} else
return false;
}
```
* `q_insert_head` 使用 `q_create_elem` 改寫:
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newelem;
bool ret = q_create_elem(q, s, &newelem);
if (ret) {
// Update q when all data are ready
if (q->head == NULL)
q->tail = newelem;
newelem->next = q->head;
q->head = newelem;
q->size++;
}
return ret;
}
```
* `q_insert_tail` 使用 `q_create_elem` 改寫:
```c=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newelem;
bool ret = q_create_elem(q, s, &newelem);
if (ret) {
// Update q when all data are ready
newelem->next = NULL;
if (q->head == NULL) {
q->head = newelem;
q->tail = newelem;
} else {
q->tail->next = newelem;
q->tail = newelem;
}
q->size++;
}
return ret;
}
```
### q_remove_head
* 使用較安全的 `strncpy` ， 避免字串沒有正確結尾 採用 `sp[bufsize - 1] = 0`
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* TODO: You need to fix up this code. */
/* TODO: Remove the above comment when you are about to implement. */
if (q) {
if (q->size > 0) {
if (q->tail == q->head)
q->tail = NULL;
if (sp) {
strncpy(sp, q->head->value, bufsize);
sp[bufsize - 1] = 0;
}
free(q->head->value);
list_ele_t *pasthead = q->head;
q->head = q->head->next;
free(pasthead);
q->size--;
return true;
} else
return false;
} else
return false;
}
```
### q_size
* 使用 `size` 欄位:
在各種操作中，務必要持續維護正確的 `size`
```c=
int q_size(queue_t *q)
{
/* TODO: Remove the above comment when you are about to implement. */
if (q)
return q->size;
return 0;
}
```
### q_reverse
* 循序走訪即可，但需要保留前一個元素位置:
前一個元素位置我保存在 `oldprev` ，當全部走訪完畢，再交換 `queue_t` 中的 `head` 與 `tail`
```c=
void q_reverse(queue_t *q)
{
/* TODO: Remove the above comment when you are about to implement. */
if (q) {
list_ele_t *curr, *oldprev, *oldnext;
curr = q->head;
oldprev = NULL;
while (curr) {
oldnext = curr->next;
curr->next = oldprev;
oldprev = curr;
curr = oldnext;
}
// Swapping
oldprev = q->head;
q->head = q->tail;
q->tail = oldprev;
}
}
```
### q_sort
* 第一版採用 bubble sort:
氣泡排序只需要用兩個迴圈，把最大的一直往後排，因此能很快實做出排序，供第二版比較使用。要進行交換時有可能會與開頭元素相關，因此我使用 Jserv 老師 在課堂提到 Linus Torvalds 的小技巧。我這邊也使用了 `prev_indirect` 來進行元素的交換。
```c=
void q_sort_slow(queue_t *q)
{
// Use bubble sort
if (q) {
list_ele_t *curr;
for (int remaining = q->size; remaining > 0; remaining--) {
curr = q->head;
list_ele_t **prev_indirect = &(q->head);
int iter = 0;
while (curr) {
iter++;
if (iter > remaining)
break;
// compare and swap
if (curr->next) {
int cmp = strcmp(curr->value, curr->next->value);
if (cmp > 0) {
list_ele_t *oldnextnext;
if (curr->next == q->tail)
q->tail = curr;
// *prev_indirect -> curr -> currnext
*prev_indirect = curr->next;
oldnextnext = curr->next->next;
curr->next->next = curr;
curr->next = oldnextnext;
}
}
prev_indirect = &(curr->next);
curr = curr->next;
}
}
}
}
```
* 第二版 merge sort (使用 `size` )
其中 merge sort 會需要將鍊結串列切成兩段，我是會利用 `size` 將串列分成前 `size/2` 元素留在`head` 其他在 `second`。
```c=
list_ele_t *list_merge_sort(list_ele_t *head, size_t size)
{
if (size < 2)
return head;
size_t firstsz = size / 2;
size_t secondsz = size - firstsz;
// split to two parts
list_ele_t *second = head;
for (int i = 0; i < firstsz - 1; i++)
second = second->next;
list_ele_t *tmp = second;
second = second->next;
tmp->next = NULL;
list_ele_t *outfirst = list_merge_sort(head, firstsz);
list_ele_t *outsecond = list_merge_sort(second, secondsz);
return join_result(outfirst, outsecond);
}
```
* 第二版 merge sort 中的 join_result
單純從頭開始尋訪，然後將兩個串列中小的元素挑出來，實做中還是會分是否為第一個元素，未來會想把此處進行修改 `if (head == NULL)` 。
```c=
list_ele_t *join_result(list_ele_t *first, list_ele_t *second)
{
if (!first)
return second;
if (!second)
return first;
list_ele_t *head = NULL;
list_ele_t *curr = NULL;
while (first && second) {
int cmp = strcmp(first->value, second->value);
if (cmp > 0) {
if (head == NULL) {
head = second;
curr = head;
} else {
curr->next = second;
curr = curr->next;
}
second = second->next;
} else {
if (head == NULL) {
head = first;
curr = head;
} else {
curr->next = first;
curr = curr->next;
}
first = first->next;
}
}
if (first) {
curr->next = first;
}
if (second) {
curr->next = second;
}
return head;
}
```
* 第二版 merge sort 遇到的 bug
在實作時，花了三四個小時除蟲也與 `bubble sort` 進行比較，但最花時間的臭蟲竟然是忘記更新 `q->head`。
```c=
void q_sort(queue_t *q)
{
if (q && q->head) {
if (q->size >= 2) {
list_ele_t *result = list_merge_sort(q->head, q->size);
q->head = result; // !! update the head
while (result) {
q->tail = result;
result = result->next;
}
}
}
}
```
### Github
* https://github.com/tungtylee/lab0-c [ca835f0f]
```
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
### 心得
第一次參與該課程作業撰寫，只有簡單將queue相關功能完成。更有趣的將會再自行學習。
* 執行時期的記憶體檢測
* Valgrind 動態程式分析工具
* dudect 工具
## 暫存區(待整理)
### pre-commit hook
* 作業說明提到引入 pre-commit hook, 因此隨意進行 commit 會跳出訊息
* Commit bad commit messages
```
$ git commit -am 'AAAA'
Following files need to be cleaned up:
queue.c
AAAA [line 1]
- Possible misspelled word(s): AAAA
- Capitalize the subject line
- Do no write single worded commits
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
Proceed with commit? [e/n/?] n
```
* clang-format 並沒有被強制使用
```
[!] queue.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i queue.c
Following files need to be cleaned up:
queue.c
```
### Static analysis: variableScope, memleak, unusedFunction
其實本專案包含使用 `cppcheck` 對開發幫助非常大，特別是 `[memleak]` ， 減少開發時期產生的臭蟲。
* [variableScope]
```
queue.c:31:32: style: The scope of the variable 'past_ele_ptr' can be reduced. [variableScope]
list_ele_t *curr_ele_ptr, *past_ele_ptr;
```
* [memleak]
```c
bool q_insert_head(queue_t *q, char *s)
{
if (!q) return false;
list_ele_t *newh;
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if(newh) {
size_t len = strlen(s);
newh->value = malloc(sizeof(char)*len);
if(newh->value) {
strncpy(newh->value, s, len);
}
else return false;
//pdate q when all data are ready
newh->next = q->head;
q->head = newh;
return true;
}
else return false;
}
```
```
queue.c
queue.c:69:13: error: Memory leak: newh [memleak]
return false;
^
Fail to pass static analysis.
```
* [unusedFunction]
```
Following files need to be cleaned up:
queue.c
queue.c:194:0: style: The function 'q_sort_slow' is never used. [unusedFunction]
^
Fail to pass static analysis.
```
### 其他
* Our computer will always crash when I try to issue `make test` twice
Sign in with Wallet
Connect another wallet