# 2021q1 Homework1 (lab0)
contributed by < `yuchun1214` >
:::danger
注意共筆書寫規範：中英文間用一個半形空白字元區隔
:notes: jserv
:::
## C Programming Lab
### queue_t
queue中除了遠本的 `list_ele_t *head` 以外，我還多加了 `list_ele_t *tail` 用來指向queue的尾端，以及 `int size` 來紀錄queue的長度。
```cpp
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
/* TODO: You will need to add more fields to this structure
* to efficiently implement q_size and q_insert_tail.
*/
list_ele_t *tail;
int size;
/* TODO: Remove the above comment when you are about to implement. */
} queue_t;
```
### q_new
```c=
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* TODO: What if malloc returned NULL? */
return (q) ? (q->tail = q->head = NULL), (q->size = 0), (q) : q;
}
```
### q_free
q_free的功能是將queue清掉。在這裡為了能夠更好的閱讀程式碼，我清掉element的函數另外寫成 `void list_ele_free(list_ele_t *ele)`
```cpp=
void list_ele_free(list_ele_t *ele)
{
if (ele) {
free(ele->value);
free(ele);
}
}
```
```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 */
if (!q) {
return;
}
list_ele_t *next;
while (q->head) {
next = (q->head)->next;
list_ele_free(q->head);
q->head = next;
}
free(q);
}
```
### q_insert_head
在 insert head 的部分我有點不太滿意自己寫的 code ，主要是底下23行的地放為了能讓 `q->tail` 能指向正確的位置，但實際上會進入 if 內只會發生在插入第一個 element 時，卻要每次 insert 時都要做 if 的判斷。
```c=
/*
* Attempt to insert element at head of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* TODO: What should you do if the q is NULL? */
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (q == NULL) {
return false;
}
newh = list_ele_new(s);
if (!newh) // fail to malloc
return false;
newh->next = q->head;
q->head = newh;
++q->size;
if (q->tail == NULL) {
q->tail = q->head;
}
return true;
}
```
### q_insert_tail
由於有天在 `queue_t` 中添加 `tail` 因此能夠很輕鬆的將 element 加入 queue 中。
```c=
/*
* Attempt to insert element at tail of queue.
* Return true if successful.
* Return false if q is NULL or could not allocate space.
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*/
bool q_insert_tail(queue_t *q, char *s)
{
/* TODO: You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
if (q == NULL) {
return false;
}
list_ele_t *newt;
newt = list_ele_new(s);
if (!newt)
return false;
if (q->tail) {
q->tail->next = newt;
} else {
q->head = newt;
}
q->tail = newt;
++q->size;
return true;
}
```
### q_remove_head
這個函數比較需要注意的是 line 18 ，因為 `strncpy` 並不會加上 `\0` 因此要自己加上
```c=
/*
* Attempt to remove element from head of queue.
* Return true if successful.
* Return false if queue is NULL or empty.
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
* The space used by the list element and the string should be freed.
*/
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 && q->size) {
list_ele_t *head = q->head;
q->head = q->head->next;
if (sp) {
strncpy(sp, head->value, (bufsize - 1) * sizeof(char));
sp[bufsize - 1] = '\0';
}
--q->size;
list_ele_free(head);
return true;
}
return false;
}
```
### q_size
```c=
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
int q_size(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* Remember: It should operate in O(1) time */
/* TODO: Remove the above comment when you are about to implement. */
return (q) ? q->size : 0;
}
```
這個函數要求要在 $O(1)$ 內完成。在這個函數裡用了一個operator來做判斷，就程式面上來看應該是 $O(1)$ ，但不知為何， `make test` 量測的結果卻不一定是constant time.於是我決定去看一下組合語言。
從組合語言看起來只差一個 `mov` 的 `instruction` 而已，但卻被判斷不一定是常數時間。
### q_reverse
實作的原理主要是將每個 element 的 next 指標轉向，指向前一個 element(line:12)
```c=
void q_reverse(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
if (!q || q->size == 0)
return;
list_ele_t *prev = q->head;
list_ele_t *iter = q->head->next;
list_ele_t *next;
while (iter && iter->next) {
next = iter->next;
iter->next = prev;
prev = iter;
iter = next;
}
if (!iter)
return;
iter->next = prev;
// swap head and tail
next = q->tail;
q->tail = q->head;
q->head = next;
q->tail->next = NULL;
}
```
### q_sort
在 q_sort 中原本我有嘗試 quick sort ，但後來想一想會了求穩定還是轉為使用 merge sort ，不過如果實際去看`queue.c`還是看得到 quick sort code 。
merge sort中主要分兩部分，分別是 `list_merge_sort` 以及 `list_merge` ，前者主要做拆分的動作，後者則是做merge。
```c=
list_ele_t *list_merge(list_ele_t *lhs, list_ele_t *rhs, list_ele_t **tail)
{
list_ele_t *result, *result_iter;
if (strcmp(lhs->value, rhs->value) < 0) {
result = lhs;
lhs = lhs->next;
} else {
result = rhs;
rhs = rhs->next;
}
result_iter = result;
while (lhs && rhs) {
if (strcmp(lhs->value, rhs->value) < 0) {
result_iter->next = lhs;
lhs = lhs->next;
} else {
result_iter->next = rhs;
rhs = rhs->next;
}
result_iter = result_iter->next;
}
while (lhs) {
result_iter = result_iter->next = lhs;
lhs = lhs->next;
}
while (rhs) {
result_iter = result_iter->next = rhs;
rhs = rhs->next;
}
*tail = result_iter;
return result;
}
```
```c=
list_ele_t *list_merge_sort(list_ele_t *head, list_ele_t **tail)
{
if (!head || !(head->next))
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
// find the middle of list
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *lhs = list_merge_sort(head, tail);
list_ele_t *rhs = list_merge_sort(fast, tail);
return list_merge(lhs, rhs, tail);
}
```
```c=
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(queue_t *q)
{
/* TODO: You need to write the code for this function */
/* TODO: Remove the above comment when you are about to implement. */
// list_quick_sort(&q->head, &q->tail);
if (q) {
q->head = list_merge_sort(q->head, &q->tail);
}
return;
}
```
總結以上函數有仔細寫大概都可以拿到100分。
## Address Sanitizer
在 `make SANITIZER=1` 並執行qtest help之後可清楚看見一些錯誤的訊息，訊息指出是 `do_help_cmd` 函數出錯。
但經肉眼檢查發現應該沒什麼問題，因此轉而檢查 `add_param` 以及呼叫 `add_param` 的code，發現問題可能是出現在這裏做的將 `int*` 指向 `bool*` 的問題，於是加以修改之後就沒問題了
## Valgrind
在 `make valgrind` 後可以看到一系列的錯問訊息指出有記憶體是 unreachable 。
實際去找出錯誤訊息的程式發現是 `strdup` 在搞鬼
`strdup manual` 中是這樣寫的：
於是我認為應該是history最後沒有清掉記憶體，但在 `static void freeHistory(void)` 中卻有寫到。
於是我開始懷疑是否是因為 `history` ~~是 global variable 的關係，因而 valgrind 在檢查時是依照函數內容去做檢查，並非全面性的檢查所有的記憶體。 但這部分仍有待確認...~~ 經過確認後發現， valgrind 的行為並非上述所說。原本我的作法是在 `.valgrindrc` 中加上 `--show-reachable=no` ，但這方式有點鴕鳥心態，這樣只是假裝看不到錯誤，並非錯誤消失了。在確認 `valgrind` 的行為後我決定找出原因。在 [linenoise.c](https://github.com/yuchun1214/lab0-c/blob/master/linenoise.c) 中，原開發者的確有寫到 [freeHistory](https://github.com/yuchun1214/lab0-c/blob/master/linenoise.c#L1191) 這些程式碼的內容沒錯，關鍵的原因在於當使用 `.cmd` 檔案當作輸入時，程式完全不會呼叫 `freeHistory` 。最簡單的解法就是在 `console.c:run_console` 結束前呼叫 `freeHistory` 即可。
<!-- ## Coroutine
我花了很多時間研究 Coroutine. 整合 [tiny-web-server](https://github.com/shenfeng/tiny-web-server) 並非難事，利用`setjmp` -->
Sign in with Wallet
Connect another wallet