# 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`加入

list_ele_t *tail;
int size;

接著開始修改**queue.c**中的function :
### **q_new** :

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** :

 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** :

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** :

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** :

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** :

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** :

{
    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** :

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)