# 2020q3 Homework1 (lab0)
contributed by < `nelsonlai1` >
## 開發環境
```
$ uname -a
Linux itlab-right 5.4.0-42-generic #46~18.04.1-Ubuntu SMP Fri Jul 10 07:21:24 UTC 2020
x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
Copyright (C) 2017 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
## function 功能
1. **q_new** : 新增queue
2. **q_free** : 釋放queue中所有記憶體
3. **q_insert_head** : 在queue最前面加入node
4. **q_insert_tail** : 在queue最後面加入node
5. **q_remove_head** : 刪除queue最前方的node，將刪除的元素存入sp中
6. **q_size** : 回傳queue大小
7. **q_reverse** : 將queue順序顛倒
8. **q_sort** : 將queue由小排到大
## 開發過程
首先依照作業要求中的提示，在**queue.h**中的`struct queue_t`加入
``` c=
list_ele_t *tail;
int size;
```
接著開始修改**queue.c**中的function :
### **q_new** :
``` c=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
q->head = q->tail = NULL;
q->size = 0;
return q;
}
```
這個function挺基本的，先分配一個queue_t大小的空間給q，若分配失敗回傳NULL，反之則對q做初始化，將head與tail都指向NULL，size設為0。
### **q_free** :
``` c=
void q_free(queue_t *q)
{
if (q == NULL)
return;
while (q->head != NULL) {
list_ele_t *tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
首先先確認q不為NULL後，在q不為empty的條件下，先將`q->head`以一個`tmp`儲存，將
`q->head`移動到下一位後，再將原本的`q->head`(tmp)釋放，最後再將q釋放。
如此一來，便能夠從頭開始輪一次後將所有node釋放。
### **q_insert_head** :
```c=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL)
return false;
newh->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newh->value == NULL) {
free(newh);
return false;
}
snprintf(newh->value, strlen(s) + 1, "%s", s);
if (q->head != NULL)
newh->next = q->head;
else {
q->tail = newh;
newh->next = NULL;
}
q->head = newh;
q->size++;
return true;
}
```
前半段(13行前)在對分配記憶體位置以及錯誤做處理，`newh->value`的部分由於"\0"字元的關係要多分配一個char的空間給它。
snprintf這個function在gcc編譯後會先將要被寫入的string(newh->value)清空，再將要寫入的string(s)補"/0"後寫入，非常適合在這次作業中使用。
接著判斷`q->head`是否存在，存在的話將`q->head` assign給`newh->next`，不存在(q為empty)時，`q->tail`也指向`newh`，同時因為`newh`是唯一一個node，故把`newh->next`指向NULL。最後無論如何都將`q->head`指向`newh`，並把`q->size`加一。
### **q_insert_tail** :
``` c=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (newt == NULL)
return false;
newt->value = malloc(sizeof(char) * (strlen(s) + 1));
if (newt->value == NULL) {
free(newt);
return false;
}
snprintf(newt->value, strlen(s) + 1, "%s", s);
newt->next = NULL;
if (q->tail != NULL)
q->tail->next = newt;
else
q->head = newt;
q->tail = newt;
q->size++;
return true;
}
```
前面與`q_insert_head`雷同，不再贅述。
後面則先把`newt->next`指向NULL，若存在`q->tail`則將`q->tail->next`指向newt，反之(q為empty)則需要更新`q->head`，與`q_insert_head`類似。
### **q->remove_head** :
``` c=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL)
return false;
if (sp != NULL)
snprintf(sp, bufsize, "%s", q->head->value);
list_ele_t *rm = q->head;
q->head = q->head->next;
free(rm->value);
free(rm);
q->size--;
if (q->size == 0)
q->tail = NULL;
return true;
}
```
首先判斷q是否為NULL或empty，是的話返回false。
再來看sp是否存在，存在時用snprintf來寫入被刪除的值，不存在則不管它。
接著的概念與`q_free`類似，不過只做一次，最後判斷如果q變成empty的話，將`q->tail`指向NULL。
### **q_size** :
``` c=
int q_size(queue_t *q)
{
if (q == NULL)
return 0;
return q->size;
}
```
判斷q是否為empty，如果是的話返回0，不是的話返回`q->size`。
這function雖然簡單，但不知為何有時候make test時會判斷為不是O(1)。
### **q_reverse** :
``` c=
{
if (q == NULL || q->head == q->tail)
return;
list_ele_t *cursor = NULL;
q->tail = q->head;
while (q->head != NULL) {
list_ele_t *next = q->head->next;
q->head->next = cursor;
cursor = q->head;
q->head = next;
}
q->head = cursor;
}
```
這個function是由quiz1改寫而來的。
首先判斷q是否不存在或是element為0或1，若是的話因為無須reverse直接`return`。令一個`cursor`指向NULL，這個`cursor`會一直跟著`q->head`移動，在`q->head`以及reverse前的`q->head`前一項轉換。
while迴圈中，首先令一個`next`儲存原本的`q->head->next`(原本第二項element)，將`q->head->next`指向`cursor`(此時`cursor`為NULL，也就是將原本的第一項改為最後一項)，將`cursor`指到`q->head`(現在為最後一項)，將`q->head`指向`next`(即將成為倒數第二項)。如此一來，最後`cursor`會指向reverse完的第一項，`q->head`則是指向NULL。
最後把`q->head`指向`cursor`。
### **q_sort** :
``` c=
void q_sort(queue_t *q)
{
if (q == NULL || q->head == q->tail)
return;
q->head = q->tail = merge_sort(q->head);
while (q->tail->next != NULL)
q->tail = q->tail->next;
}
list_ele_t *merge_sort(list_ele_t *head)
{
if (head == NULL || head->next == NULL)
return head;
list_ele_t *fast = head->next;
list_ele_t *slow = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;
slow->next = NULL;
list_ele_t *l1 = merge_sort(head);
list_ele_t *l2 = merge_sort(fast);
return merge(l1, l2);
}
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
list_ele_t *head = NULL;
list_ele_t **tmp = &head;
while (l1 != NULL && l2 != NULL) {
if (strcmp(l1->value, l2->value) < 0) {
*tmp = l1;
tmp = &(*tmp)->next;
l1 = l1->next;
} else {
*tmp = l2;
tmp = &(*tmp)->next;
l2 = l2->next;
}
}
if (l1 != NULL)
*tmp = l1;
if (l2 != NULL)
*tmp = l2;
return head;
}
```
由於作業要求O(nlgn)，首先會決定要用quicksort或mergesort，但考慮到quicksort若不做處理的話會在worst case時變成O(n^2)，且在linked list實作也較麻煩，這裡使用mergesort。
一開始想到既然已經定義`q->size`以及諸多function，於是直接建立額外的queue來進行mergesort，但沒想到在make test時直接失敗了，應該是使用太多的記憶體空間，但又不忍心刪掉，只好放在註解中。
最後只好乖乖~~抄襲~~參考老師提供的[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)做改寫。為了recursive需求，另外令兩個function(同時也要在**queue.h**新增)
在`merge_sort`中，先定義終止條件，當元素為0或1時回傳`head`。接著的技巧利用`fast`速度為`slow`的兩倍，當`fast`跑到末端時，`slow`會位於中間，再將`fast`指向`slow->next`變成後半段，而`slow->next`指向NULL來將前半段分割出來。
`merge`中，以一個`head`以及`head`的pointer `tmp`來將`l1`, `l2`整合排序，使用`tmp`的原因是為了不讓`head`位置跑掉。while迴圈內將`l1`為頭的list, `l2`為頭的list做比較，並依序將`*tmp`指向小的元素，最後當一方沒了時，將`*tmp`指向剩餘的一方，最後return `head`時就會是排序好的。
## Valgrind & Massif
首先輸入
```
make valgrind
```
執行Valgrind
接著用
```
valgrind --tool=massif ./qtest -v 3 -f traces/trace-eg.cmd
```
執行Massif
```
cmd>
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
q = [dolphin]
cmd> ih bear
q = [bear dolphin]
cmd> ih gerbil
q = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
q = [gerbil bear dolphin meerkat]
cmd> it bear
q = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
q = [bear meerkat dolphin bear gerbil]
cmd> # See how long it is
cmd> size
Queue size = 5
q = [bear meerkat dolphin bear gerbil]
cmd> # Delete queue. Goes back to a NULL queue.
cmd> free
q = NULL
cmd> # Exit program
cmd> quit
Freeing queue
```
再輸入
```
ms_print massif.out.[數字](輸出的檔案名)
```
來看massif分析結果
```
--------------------------------------------------------------------------------
Command: ./qtest -v 3 -f traces/trace-eg.cmd
Massif arguments: (none)
ms_print arguments: massif.out.14570
--------------------------------------------------------------------------------
KB
11.16^ #
| : :::@:@::#:
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| ::@::@:::::::: @ @::#::
| @::@::@:::::::: @ @::#::@
0 +----------------------------------------------------------------------->ki
0 314.8
Number of snapshots: 56
Detailed snapshots: [4, 10, 18, 37, 41, 47 (peak), 54]
```
詳細的記憶體使用狀況，這裡只列出一部分
```
--------------------------------------------------------------------------------
n time(i) total(B) useful-heap(B) extra-heap(B) stacks(B)
--------------------------------------------------------------------------------
0 0 0 0 0 0
1 209,271 40 32 8 0
2 211,027 544 416 128 0
3 212,471 704 544 160 0
4 214,104 824 640 184 0
77.67% (640B) (heap allocation functions) malloc/new/new[], --alloc-fns, etc.
->77.67% (640B) 0x10B4CF: malloc_or_fail (report.c:189)
->58.25% (480B) 0x10BFE1: add_cmd (console.c:123)
| ->03.88% (32B) 0x10AD05: main (qtest.c:82)
| |
| ->03.88% (32B) 0x10AD1F: main (qtest.c:83)
| |
| ->03.88% (32B) 0x10AD39: main (qtest.c:84)
| |
| ->03.88% (32B) 0x10AD53: main (qtest.c:87)
| |
| ->03.88% (32B) 0x10AD6D: main (qtest.c:90)
| |
| ->03.88% (32B) 0x10AD87: main (qtest.c:93)
| |
| ->03.88% (32B) 0x10ADA1: main (qtest.c:96)
| |
| ->03.88% (32B) 0x10ADBB: main (qtest.c:97)
| |
| ->03.88% (32B) 0x10C0C2: init_cmd (console.c:93)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C0DC: init_cmd (console.c:94)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C0F6: init_cmd (console.c:96)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C110: init_cmd (console.c:97)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C12A: init_cmd (console.c:99)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C144: init_cmd (console.c:100)
| | ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
| |
| ->03.88% (32B) 0x10C15E: init_cmd (console.c:101)
| ->03.88% (32B) 0x10ACEB: main (qtest.c:759)
|
->19.42% (160B) 0x10C057: add_param (console.c:144)
->04.85% (40B) 0x10C17D: init_cmd (console.c:102)
| ->04.85% (40B) 0x10ACEB: main (qtest.c:759)
|
->04.85% (40B) 0x10C19C: init_cmd (console.c:104)
| ->04.85% (40B) 0x10ACEB: main (qtest.c:759)
|
->04.85% (40B) 0x10C1BB: init_cmd (console.c:105)
| ->04.85% (40B) 0x10ACEB: main (qtest.c:759)
|
->04.85% (40B) 0x10C1DA: init_cmd (console.c:106)
->04.85% (40B) 0x10ACEB: main (qtest.c:759)
```
Sign in with Wallet
Connect another wallet