# 2020q3 Homework1 (lab0)
contributed by < `RainbowEye0486` >

## Outline
[TOC]

## 開發環境

$ uname -a
Linux hastur-Swift-SF314-56G 5.4.0-47-generic #51~18.04.1-Ubuntu SMP Sat Sep 5 14:35:50 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.

## 作業需求
queue.c 僅提供介面但尚未有完整程式實作，需要補完並逐步精進，包含以下：

1. `q_new`: 建立新的「空」佇列;
2. `q_free`: 釋放佇列所佔用的記憶體;
3. `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
4. `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
5. `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
6. `q_size`: 計算佇列中的元素數量。
7. `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
8. `q_sort`: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法
:::success
:warning: **限制 `q_size()` 以及 `q_insert_tail()` 能以$O(1)$ 時間完成**
:::

## 開發紀錄
### 9/15 q_new
新增一個 queue 的節點，用於初始化 struct 內部的所有變數，需要特別注意 malloc 回傳值為 NULL 的情形。之前使用 malloc 的時候，我沒有遇到過回傳值是NULL的情況，於是我找了一下資料，在何種情況之下有可能回傳 NULL [^one]，除了 size 是0的情形，也有可能是記憶體劃分的 stack 滿了所以無法再繼續分配記憶體。
實做時須注意到**哪些參數**是需要被初始化的

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q==NULL){
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

### 9/15 q_free
這邊我先使用第一版本的程式碼，為了先測試程式的正確性先編寫一個比較直覺的版本，主要是對於 list_ele_t struct 內部分配的 string 記憶體空間進行清除並移動到下一個節點。希望能夠找到更加精簡的版本。

void q_free(queue_t *q)
{
    while (q->head != NULL){
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

### 9/15 q_insert_head
比較直覺的是先分配一個記憶體空間，然後再更動指標，將 `q->head` 重新指向新的節點

:::success
:warning: 老師提到須注意 `strcpy` 可能產生的問題，最有可能的問題就是萬一輸入字串超過分配給複製目標字串的記憶體空間怎麼辦？如:

char str1[10];
char str2[]="abcdefghijklmn";
strcpy(str1,str2);

此情形一般來說有幾種解決方式，第一種是先抓取複製字串的長度＋1(因為還要算進中止符號/0)，然後才分配相對應的記憶體空間，另一種方式是移除不安全的` strcpy` 本身，改用 `strlcpy` 或是 `strncpy` ，我使用的是後者，可能會發生的另一個問題是，使用`strncpy`須特別注意 `strncpy` 只會複製前面n個字符，超過的不會繼續複製，雖然這可以避免溢位的問題，但是從另一個方面看，也須特別注意如果被複製的字串過長，中止字符/0可能沒有被複製進去目標字串內。

我這邊還有查到一篇[用memcpy實做的文章](http://www.cppblog.com/Tim/archive/2011/04/02/143259.aspx)，似乎是作者認為直接搬動記憶體而不去檢查/0是否存在的話能夠節省非常多的效能，我認為這有機會遭受使用者的惡意攻擊，例如輸入 `"stop here/0 ha ha got you"` 之類的。
:::

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL){
        return false;
    }
    list_ele_t *newh;
    char *newc;
    newh = malloc(sizeof(list_ele_t));
    /* Deal with /0 in the tail of char * newc */
    if (newh == NULL){
        return false;
    }
    newc = malloc(sizeof(char) * (strlen(s) + 1));
    if (newc == NULL){
        free(newh);
        return false;
    }
    /* Situation that call to malloc returns NULL */
    strncpy(newc, s, strlen(s) + 1);
    newh->value = newc;
    newh->next = q->head;
    q->head = newh;
    /* Deal with new add data structures */
    if (q->size == 0){
        q->tail = newh;
    }
    q->size++;
    return true;
}

### 9/15 q_insert_tail
實做方式基本上前面跟 q_insert_head 十分接近，但是後面的串接方式變成是改到尾端。

newh->next = q->head;
q->head = newh;
/* Deal with new add data structures */
if (q->size == 0) {
    q->tail = newh;
}
q->size++;

### 9/15 q_remove_head
這邊主要是希望能夠先將 `q->head->value` 的值存取在 `sp` 裡面，並且將 `q->head` 刪除。
:::success
:warning:注意字串長度若是大於給定的 bufsize ，多餘的字符便不再存取以免溢位
:::

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->head == NULL || sp == NULL) {
        return false;
    }
    /*
    Because we can't not sure the cosistency of value and sp , we need to
    prevent overflow of sp
    */
    if (bufsize > strlen(q->head->value)) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[strlen(q->head->value)] = '/0';
    }else{
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize] = '/0';
    }
    list_ele_t *tmp = q->head;
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    /* If q is empty */
    if (q->head == NULL) {
        q->tail = NULL;
    }

    q->size--;
    return true;
}

### 9/15 q_reverse
作業要求不能配置多餘的記憶體空間，也就是說，我們不能夠新增一個一模一樣的 queue 然後一個一個重新串接，也不能用 stack push pop 的方式操作，因此我使用兩個額外的 pointer 來表示前後的關係，比較需要注意的是，要怎麼連接 next 先後的順序非常重要，不然很有可能會遺失下一個節點的位置，導致"斷開"。

void q_reverse(queue_t *q)
{
    if (q && q->size>0) {
        list_ele_t *current , *current_next;
        q->tail = q->head;
        current =  q->head;
        current_next = current->next;
        while (current_next != NULL) {
            q->head = current_next;
            current_next = q->head->next;
            q->head->next = current;
            current = q->head;
        }
        q->tail->next = NULL;
    }   
}

:::info
**問題**：之前在檢查 coding style 的時候發現 if 的後面如果不接 else 好像不會給過，這個是否是正常現象？
:::

## 9/16 q_sort
看完老師給的[Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)，決定使用效能高的merge sort，按照psudo code重新改寫了一遍，但是無論如何測試測資的時候都沒有變化，也沒有印出我新增的錯誤訊息，後來跟同學討論了之後發現是沒有重新 `$ make` 的問題，根據makefile內的敘述，可能是因為當舊有的.o檔存在時，執行 `$ make test` 的時候並不會重新建立新的.o檔，而是直接從舊的拿來用，所以某些情況下必須重新`$ make`才會更新 reference 的檔案(好吧我也沒有很確定我說的是不是對的，等待老師的指教)

重新 `$ make` 了之後，發現測資16硬是過不了，錯誤訊息如下：

+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
Error limit exceeded.  Stopping command execution
---	trace-16-perf	0/6

void q_sort(queue_t *q)
{
    if (!q || q->size <= 1) {
        return;
    }
    q->head = merge_sort_list(q->head);

    while(q->tail->next){
        q->tail = q->tail->next;
    }
    return;
}


list_ele_t *merge_sort_list(list_ele_t *head)
{
    if (!head || !head->next) {
        return head;
    }
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    /* spilt list */
    while(fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    list_ele_t *l1 = merge_sort_list(head);
    list_ele_t *l2 = merge_sort_list(fast);
    return merge(l1, l2);
}

/*
*Merge sort usage, merge two short lists into a longer one
*/
list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{   
    list_ele_t q;
    list_ele_t *temp = &q;
    while (l1 && l2) {
        if (strcmp(l1->value, l2->value) < 0) {
            temp->next = l1;
            temp = temp->next;
            l1 = l1->next;
        } else {
            temp->next = l2;
            temp = temp->next;
            l2 = l2->next;
        }
    }
    if (l1) temp->next = l1;
    if (l2) temp->next = l2;
    
    return q.next;
}

後來發現是第42行的比對出錯，原先的寫法沒辦法完全比對，字串長度會出現沒有按照遞增的方式排序。

實做結果：
100分

## Valgring & Massif 實作

當測資過100之後，下` $ make valgrind`指令得到：

hastur@hastur-Swift-SF314-56G:~/linux2020/lab0-c$ make valgrind
# Explicitly disable sanitizer(s)
make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/hastur/linux2020/lab0-c'
rm -f qtest.o report.o console.o harness.o queue.o random.o dudect/constant.o dudect/fixture.o dudect/ttest.o .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
  CC	qtest.o
  CC	report.o
  CC	console.o
  CC	harness.o
  CC	queue.o
  CC	random.o
  CC	dudect/constant.o
  CC	dudect/fixture.o
  CC	dudect/ttest.o
  LD	qtest
make[1]: Leaving directory '/home/hastur/linux2020/lab0-c'
cp qtest /tmp/qtest.TJ74F4
chmod u+x /tmp/qtest.TJ74F4
sed -i "s/alarm/isnan/g" /tmp/qtest.TJ74F4
scripts/driver.py -p /tmp/qtest.TJ74F4 --valgrind 
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---	trace-02-ops	6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---	trace-03-ops	6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, and sort
---	trace-04-ops	6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, and sort
---	trace-05-ops	5/5
+++ TESTING trace trace-06-string:
# Test of truncated strings
---	trace-06-string	6/6
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
---	trace-07-robust	6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---	trace-08-robust	6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---	trace-09-robust	6/6
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
---	trace-10-malloc	6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
---	trace-11-malloc	6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
---	trace-12-malloc	6/6
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---	trace-13-perf	6/6
+++ TESTING trace trace-14-perf:
# Test performance of size
---	trace-14-perf	6/6
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
---	trace-15-perf	6/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
---	trace-16-perf	6/6
+++ TESTING trace trace-17-complexity:
# Test if q_insert_tail and q_size is constant time complexity
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.TJ74F4 --valgrind -t <tid>

透過[massif-visualizer](https://github.com/KDE/massif-visualizer)分析得到測試17記憶體分配圖形：

[^one]:stackoverflow上對於 [malloc return NULL](https://stackoverflow.com/questions/9101597/under-what-circumstances-can-malloc-return-null) 的討論

## Timelog
忘記紀錄之前看影片及查資料的時間，所以從開始實做的時間計算起
| 開始時間 | 結束時間 | 完成進度 |
| --- | --- | ------ |
| 9/14 11:20| 9/15 1:39| 看完作業敘述，實做q_new 、 q_size|
| 9/15 10:05| 9/15 12:37| q_insert_head 、 q_free|
| 9/15 21:45| 9/16 0:07| q_reverse 、測資到54分|
| 9/16 22:12| 9/17 1:15| q_sort 、測資到94分|
| 9/17 15:35| 9/17 18:21| 開始研究 Valgrind |
| 9/17 23:06| 9/18 1:09| 基本題完成|
## TODO
- [x] queue.c/queue.h
- [x] q_new
- [x] q_free
- [x] q_remove_head
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_size
- [x] q_reverse
- [x] q_sort
- [ ] 以 Valgrind 分析記憶體問題
- [x] 引入Git pre-commit hook
- [x] 使用git-good-commit

## 參考資料及註腳