# 2020q3 Homework1 (lab0)
contributed by < `chewei3` >
## Outline
## 作業要求
在 ``queue.[ch]`` 中完成以下實作
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素
# 實作
## queue.h
* 修改 `queue_t` ，加入 `list_ele_t *tail` 及 `int size` 使得`q_size`以及 `q_insert_tail` 能夠在 $O(1)$ 時間完成
* 加入 `list_ele_t *tail` 的缺點是使用的記憶體空間增加， queue operation 需要維護 `q->tail`
```c=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
## queue.c
### q_new
建立新的 queue ，需考慮 malloc 失敗的情況
```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_free
釋放 queue 的所有記憶體，需檢查
* queue是否為NULL
* free value
* free node
```c=
void q_free(queue_t *q)
{
if (!q) return;
list_ele_t *head = q->head;
while (head) {
q->head = head->next;
free(head->value) ;
free(head);
head = q->head;
}
free(q);
}
```
### q_insert_head
插入新的 node 到 queue 的 head ，需考慮
* node malloc 失敗直接return
* node->value malloc失敗需要 free node
* 若 queue 為空，要 assign `q->tail` `list_ele_t *newh`
因為用 strcpy 將 `char *s` copy 到 node->value 會報錯，所以參考 `qtest.c` 使用 `strncpy`
```c=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (!q) return false;
/* TODO: What should you do if the q is NULL? */
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
size_t len = strlen(s) + 1;
newh->value = (char *)malloc( len * sizeof(char));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len);
/* 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;
if (!q->size)
q->tail = newh;
q->size++;
return true;
}
```
### q_insert_tail
因為有額外記住 `q->tail`，所以可以用 $O(1)$ 時間插入
作法跟 `q_insert head` 類似
```c=
bool q_insert_tail(queue_t *q, char *s)
{
if (!q) return false;
/* TODO: What should you do if the q is NULL? */
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
size_t len = strlen(s) + 1;
newh->value = (char *)malloc( len * sizeof(char));
newh->next = NULL;
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len);
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (!q->size)
q->head = newh;
else
q->tail->next = newh;
q->tail = newh;
q->size++;
return true;
}
```
### q_remove_head
* 若 `char *sp` 非空，需要 assign `head->value` 給它
```c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *head = q->head;
q->head = q->head->next;
q->size--;
if (head->value) {
if (sp) {
size_t len = bufsize > strlen(head->value) ? strlen(head->value) : bufsize - 1;
strncpy(sp, head->value, len);
sp[len] = '\0';
}
free(head->value);
}
free(head);
return true;
}
```
### q_size
```c=
int q_size(queue_t *q)
{
return q ? q->size : 0;
}
```
### q_reverse
跟 [quiz1](https://hackmd.io/@sysprog/rJ7WDWNVv) 的作法相同，需額外維護 `q->tail`
```c=
void q_reverse(queue_t *q)
{
if (!q || !q->head)
return;
list_ele_t *cursor = NULL;
q->tail = q->head;
while (q->head) {
list_ele_t *next = q->head->next;
q->head->next = cursor;
cursor = q->head;
q->head = next;
}
q->head = cursor;
}
```
### q_sort
參考 [作業說明連結](https://npes87184.github.io/2015-09-12-linkedListSort/) 使用MergeSort，後來有看到 [Zhumon](https://hackmd.io/@ZhuMon/lab0-c) 的 merge可以將 merge 及 merge_sort合併
* TODO: 合併 merge 及 merge_sort
```c=
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *tmp = NULL;
if (strcmp(l1->value, l2->value) <= 0) {
tmp = l1;
l1 = l1->next;
} else {
tmp = l2;
l2 = l2->next;
}
list_ele_t *head = tmp;
while (l1 && l2) {
if (strcmp(l1->value, l2->value) <= 0) {
tmp->next = l1;
tmp = tmp->next;
l1 = l1->next;
} else {
tmp->next = l2;
tmp = tmp->next;
l2 = l2->next;
}
}
if (l1) tmp->next = l1;
if (l2) tmp->next = l2;
return head;
}
void merge_sort(list_ele_t **head)
{
if (!*head || !(*head)->next)
return;
list_ele_t *fast = (*head)->next;
list_ele_t *slow = *head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
merge_sort(head);
merge_sort(&fast);
*head = merge(*head, fast);
}
```
# Valgrind
*待補*
還沒有看這部分，目前只有把結果跑出來
### trace-17-complexity 結果
# Perf
因為 trace-17 有時候不會通過，用 [Perf](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FB11109rdg) 去看效能瓶頸在哪
結果發現 `q_insert_head` 佔據了 15.7% 的執行時間，但是在 trace-17 裡面並沒有 `insert_head`
*待補*
Sign in with Wallet
Connect another wallet