# 2020q1 Homework1 (lab0)
contributed by < `DaDa0413` >
其他學習心得: [Makefile閱讀筆記](https://hackmd.io/@DaDa0413/EZMakeFile)
## queue.c實做
前面6個 function 花一點時間便完成，但 q_sort() 重做了1次又debug一整天:cry:
:::danger
中英文之間需要以一個半形空白字元區隔 (即 ==` `==)，在作業要求已清楚描述，務必遵守。
快去改！
:notes: jserv
:::
### q_new()
建立一個新的 Empty queue
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
// If nothing return by malloc, just return NULL
if (q == NULL) {
printf("ERROR: q_new() failed\n");
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
printf("INFO: q new success\n");
return q;
}
```
### q_free()
除了要釋放 queue 的 header ，也要釋放所有 list element 的記憶體空間。
```cpp
void q_free(queue_t *q)
{
// Free all the list element and the head of the queue
if (q == NULL) {
return;
}
list_ele_t *current_ptr = q->head;
list_ele_t *next = NULL;
while (current_ptr != NULL) {
next = current_ptr->next;
// Free the memory used by string and list elements
free(current_ptr->value);
free(current_ptr);
current_ptr = next;
}
free(q);
}
```
### q_insert_head()
遇到 NULL queue 便直接回傳`false`。
否則便回傳`true`分配記憶體給新的element，以及維護queue的架構。
```cpp
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
printf("ERROR: Insert head to a NULL queue\n");
return false;
}
list_ele_t *newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
// If queue is allocated at this time
printf("ERROR: allocate newh fail\n");
return false;
}
unsigned int s_lenth = strlen(s);
newh->value = malloc(sizeof(char) * (s_lenth + 1));
// If fail to allocate space for value
if (newh->value == NULL) {
printf("ERROR: allocate newh->value fail\n");
free(newh);
// If queue is allocated at this time
return false;
}
strncpy(newh->value, s, s_lenth);
newh->value[s_lenth] = '\0';
// Maintain the queue structure
newh->next = q->head;
q->head = newh;
if (q->size == 0)
q->tail = newh;
q->size += 1;
return true;
}
```
### q_insert_tail()
```c
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL) {
printf("ERROR: Insert tail to a NULL queue\n");
return false;
}
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
unsigned int s_lenth = strlen(s);
newh->value = malloc(sizeof(char) * (s_lenth + 1));
// If fail to allocate space for value
if (newh->value == NULL) {
free(newh);
return false;
}
strncpy(newh->value, s, s_lenth);
newh->value[s_lenth] = '\0';
// Maintain the queue structure
newh->next = NULL;
if (q->size != 0)
q->tail->next = newh;
if (q->size == 0)
q->head = newh;
q->tail = newh;
q->size += 1;
return true;
}
```
### q_size()
直接在 insert 以及 remove 時紀錄 queue 的大小，來讓 q_size() 能達成 O(1)
```c
int q_size(queue_t *q)
{
// Return the queue size we take down
if (q == NULL) {
printf("ERROR: No size of a NULL queue\n");
return 0;
}
return q->size;
}
```
### q_reverse()
使用`current_ptr`、`prev_ptr`和`next_ptr`，來指向當前的 *element* ，前一個 *element* 以及下一個 *element* ，再將`current_ptr`的指標方向從`next_ptr`轉向`prev_ptr`。當全部的 *element* 完成以後，再將 queue 的 head 以及 tail 轉向。
```c
void q_reverse(queue_t *q)
{
if (q == NULL) {
printf("ERROR: Reverse a NULL queue\n");
return;
}
list_ele_t *prev_ptr = NULL;
list_ele_t *current_ptr = q->head;
list_ele_t *next_ptr = NULL;
while (current_ptr != NULL) {
next_ptr = current_ptr->next;
current_ptr->next = prev_ptr;
prev_ptr = current_ptr;
current_ptr = next_ptr;
}
// Maintain the queue structure
list_ele_t *tmp = q->tail;
q->tail = q->head;
q->head = tmp;
}
```
### 修改q_sort()
目前使用的字串比較函式是`strcmp()`，而排序方法為 bubble sort ，但是當我測試`trace-15-perf.cmd`時，花了10分鐘仍然跑不出來，因此首先我將會把 strcmp 改成作業說明所提及的 natural sort，
```c
void q_sort(queue_t *q)
{
// Handling NULL queue
if (q == NULL) {
printf("ERROR: q sort a NULL queue\n");
return;
}
// Accroding to ascending order, bubble sort the queue
list_ele_t *roundend = q->tail;
while (roundend != q->head) {
list_ele_t *current = q->head;
while (current != roundend) {
/* if current element is bigger than next element
/ then swap the values of the two.
/
/ Tricky solution: Swap the VALUE instead of LIST ELEMENT,
/ it will reduce several pointer re-assignment into three.
*/
if (strcmp(current->value, current->next->value) > 0) {
char *temp;
temp = current->next->value;
current->next->value = current->value;
current->value = temp;
}
if (current->next == roundend)
roundend = current;
else
current = current->next;
}
}
}
```
發現 bubble sort 真的慢:sleeping:，因此改以 iterative merge sort 實作:
1. 以 botton up 的方法，來達成原本要用 recursive 完成的 merge sort。
2. 設定一個變數`interval`，初始為1，用來表示當前要 merge 的 *sub-list* 的長度，每一次合併(稱為一個 **round** )兩個長度為`interval`的 *list* ，合併完成後在合併下兩個 *sub-list* ，當整個 list 的 *sub-list* 都被合併以後，將`interval`乘以2，並再重複上述動作
3. 設定了4個 pointer 來引導 merge sort
* `prv`:指向上一 **round** 的最後一個 *element*
* `nxt`:這一 round 的下一個 *element*
* `cur1`:要合併的第一個 *sublist*
* `cur2`:要合併的第二個 *sublist*
4. 為了避免多餘的記憶體分配，直接將既有的 *element* 放入暫存的 list ，因此新增了 q_insert_element_to_tail() 。
```c
void q_sort(queue_t *q)
{
if (q == NULL || q_size(q) == 0 || q_size(q) == 1)
return;
// In order to avoid to extra line to handle head element
// case, we maintain a pseudo head.
list_ele_t pseudo;
pseudo.next = q->head;
for (unsigned int interval = 1; interval < q_size(q); interval *= 2) {
// prv is the last element of previous round
// nxt is the first element of next round
// next_prv will record where prv will move to
list_ele_t *prv = &pseudo;
list_ele_t *nxt = pseudo.next;
while (nxt != NULL) {
// cur1 and cur2 lead two lists to be sorted
list_ele_t *cur1 = prv->next;
list_ele_t *cur2 = cur1;
for (unsigned int i = 0; cur2 != NULL && i < interval; ++i)
cur2 = cur2->next;
// move next_prv and nxt to correct place
nxt = cur2;
for (unsigned int i = 0; nxt != NULL && i < interval; ++i)
nxt = nxt->next;
queue_t merge = {.head = NULL, .tail = NULL, .size = 0};
// cur1_end and cur2_end is the next element of each list
list_ele_t *cur1_end = cur2;
list_ele_t *cur2_end = nxt;
while (cur1 != cur1_end || cur2 != cur2_end) {
if (cur2 == cur2_end ||
(cur1 != cur1_end &&
strnatcmp(cur1->value, cur2->value) < 0)) {
list_ele_t *tmp1 = cur1;
cur1 = cur1->next;
q_insert_element_to_tail(&merge, tmp1);
} else {
list_ele_t *tmp2 = cur2;
cur2 = cur2->next;
q_insert_element_to_tail(&merge, tmp2);
}
}
prv->next = merge.head;
prv = merge.tail;
merge.tail->next = nxt;
q->tail = merge.tail;
}
}
q->head = pseudo.next;
}
```
## 開發問題
1. **Problem:**
```c
bool q_insert_head(queue_t *q, char *s)
```
以及
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
```
會出現 char *s 以外的亂碼
**Solution:**
查閱網路[ Cplusplus ](http://www.cplusplus.com/reference/cstring/strncpy/)上，查閱到 strncpy() 的錯誤使用方法，strncpy() 並不會自動在字串結尾加入`'\0'`。
ISO/IEC 9899:201 提到關於 strncpy 的敘述:
>The strncpy function copies not more than n characters (characters that follow a null
character are not copied) from the array pointed to by s2 to the array pointed to by s1.
但沒有講明是否有複製 `'\0'`，因此最後在他人整理過得資料[字串長度、複製、串接](https://openhome.cc/Gossip/CGossip/StringLengthCopyCat.html)中得出需要自行加入
:::warning
查閱資料需要指明出處，並儘量以第一手資料為主，說好的 C 語言規格書呢？
:notes: jserv
:::
2. **Problem:**
**Solution:**
使用 *Valgrind* 分析
很明顯的告訴我們，在`q_insert_head()`被 allocate 的 block 還是 reachable 。因此得知， Free 一個 list element 時，不會將被 allocate 的空間也自動 free 掉，因此必須要
```c
free(list_element->value);
free(list_element);
```
3. **Problem**:
執行 trace-07-robust.cmd ，測試 insert head to NULL queue 時，不斷發生 segmentation fault 。即使在`q_insert_head()`的最後一行加入
```c=98
printf("%s\n", q->head->value);
```
仍可以正常的印出字串
**Solution:**
運用 *Valgrind* ，分析記憶體 Segmentation fault 的原因，發現出錯的地方式在 qtest.c 的
```c=215
if (!q->head->value) {
```
開始去思考此 q 跟我在`q_insert_head()`中引入的q是否視同一個。
才發現搞錯題目的意思，當insert head或insert tail遇上 NULL queue 時，直接返回 fasle 即可，不須額外的`q_new()`，因此對`q_insert_head()`做以下更動
```clike
bool q_insert_head(queue_t *q, char *s)
{
/* TODO: What should you do if the q is NULL? */
- // Dada: Call q_new() and handle the NULL case
- bool q_was_NULL = false;
if (q == NULL) {
- q_was_NULL = true;
- if ((q = q_new()) == NULL)
- return false;
+ printf("ERROR: Insert head to a NULL queue\n");
+ return false;
}
```
:::danger
文字訊息不要用圖片展現，可善用 `diff -up` 輸出程式碼之間的差異。
:notes: jserv
:::
Sign in with Wallet
Connect another wallet