# 2022q1 Homework1 (lab0)
contributed by < `Korin777` >
## 開發環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ lscpu
Architecture:                    x86_64
CPU op-mode(s):                  32-bit, 64-bit
Byte Order:                      Little Endian
Address sizes:                   39 bits physical, 48 bits virtual
CPU(s):                          8
On-line CPU(s) list:             0-7
Thread(s) per core:              2
Core(s) per socket:              4
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           142
Model name:                      Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
Stepping:                        10
CPU MHz:                         1800.000
CPU max MHz:                     3400.0000
CPU min MHz:                     400.0000
BogoMIPS:                        3600.00
Virtualization:                  VT-x
L1d cache:                       128 KiB
L1i cache:                       128 KiB
L2 cache:                        1 MiB
L3 cache:                        6 MiB
NUMA node0 CPU(s):               0-7

## queue.c 實作

### q_new
* 一開始我是直接 `malloc` 一個 `head` 並回傳 , 後來發現這樣就無法透過 `list.h` 所提供的 `list_empty` 來判斷 list 是否為空 , 且這樣的 linked list 也並不是雙向環狀的
* 後來透過 `list.h` 提供的 `INIT_LIST_HEAD` 將 `head` 的 `prev` 及 `next` 都指向自己 , 完成雙向環狀的 linked list

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head)
        return NULL;
    INIT_LIST_HEAD(head);
    return head;
}

### q_free
* 透過 `list.h` 提供的 `list_for_each_entry_safe` 遍歷 list 並釋放每個 `entry` 所配置過的記憶體空間
* list 的每個 `entry` 皆為 `element_t`
* 一個 `entry` 要先釋放 `element_t ->value` 在釋放 `element_t`
* 最後還要再釋放 list 的 `head` , 因為它並不是 `list` 中的一個 `entry` 而是用來當作 list 的開頭

void q_free(struct list_head *l)
{
    if (!l)
        return;
    element_t *ele, *tmpele;
    list_for_each_entry_safe (ele, tmpele, l, list)
        free(ele->value), free(ele);
    free(l);
}

### q_insert_head
* `malloc` 一個 `element_t` 作為 list 中一個 `entry`
* `element_t->value` 的 size 為 `strlen(s)+1` , 最後一個字元用來存放空字元 `\0`
* `element_t->list` 是 `struct list_head` 的型態 , 為實際 linked list 互相連接的節點 , 透過 `list.h` 提供的 `list_add` 來將它加在 linked list 的最前面(不包含`head`)
* 當配置 `element_t ->value` 記憶體失敗時 , 要釋放`element_t` 的記憶體 , 才不會產生 memory leak
* 特別用一個 `len` 變數來儲存 `s` 的長度 , 減少重複呼叫 `strlen` 所花的時間 , 不過在測試 time complexity 有時還是會沒通過
* 後來發現 time complexity 沒過得原因在 q_reverse 寫錯了

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    int len = strlen(s);
    ele->value = malloc(len + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }
    strncpy(ele->value, s, len);
    ele->value[len] = '\0';
    list_add(&ele->list, head);
    return true;
}

### q_insert_tail
* 和 `q_insert_head` 差再需用 `list.h` 提供的`list_add_tail` 來連接節點

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *ele = malloc(sizeof(element_t));
    if (!ele)
        return false;
    int len = strlen(s);
    ele->value = malloc(len + 1);
    if (!ele->value) {
        free(ele);
        return false;
    }
    strncpy(ele->value, s, len);
    ele->value[len] = '\0';
    list_add_tail(&ele->list, head);
    return true;
}

### q_remove_head
* 透過 `list.h` 所提供的 `list_entry` , 有了包含在 `element_t` 中的 `list` 記憶體位置 , 就能算出此 `element_t` 的記憶體位置
* 將 `element_t->value` 複製到 `sp` 並將最後一個字元設為空字元 `\0`
* 透過 `list.h` 所提供的 `list_del` , 將節點移除

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->next;
    element_t *ele = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return ele;
}

### q_remove_tail
* 和 `q_remove_head` 差在移除的節點為 `head->prev`

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    struct list_head *node = head->prev;
    element_t *ele = list_entry(node, element_t, list);
    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(node);
    return ele;
}

### q_size
* 透過 `list.h` 提供的 `list_for_each` 遍歷 linked list 來取長度

int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int len = 0;
    struct list_head *li;

    list_for_each (li, head)
        len++;
    return len;
}

### q_delete_mid
* `h` 一開始為第一個節點 , `t` 一開始為最後一個節點
* `h` 一直往後走 , `t` 則一直往前走 , 當兩者相同或 `h->next` 與 `t` 相同時 , `h` 恰好為中點

bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;
    struct list_head *h = head->next, *t = head->prev;
    while (h != t) {
        if (h->next == t)
            break;
        h = h->next, t = t->prev;
    }
    element_t *ele = list_entry(h, element_t, list);
    list_del(h);
    free(ele->value), free(ele);
    return true;
}

### q_delete_dup
* `tmp` 為字元指標 , 配置記憶體前 `tmp` 不為 NULL 要先釋放 `tmp` 的記憶體 , 以免產生 memory leak
* `tmp`為 NULL 或 `tmp` 和當前 `entry` 的字串不同 , 就看下個 `entry` 的字串是否與當前字串一樣 , 來判斷是否該移除當前節點及釋放對應的記憶體
* `tmp` 和當前 `entry` 的字串相同 , 直接移除當前節點及釋放對應的記憶體
* 若 `tmp` 最後不為 NULL 要釋放 `tmp` 記憶體

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    char *tmp = NULL;
    element_t *ele, *tmpele;
    list_for_each_entry_safe (ele, tmpele, head, list) {
        if (!tmp || strcmp(tmp, ele->value) != 0) {
            if (ele->list.next && ele->list.next != head) {
                element_t *elen = list_entry(ele->list.next, element_t, list);
                if (strcmp(elen->value, ele->value) == 0) {
                    if (tmp)
                        free(tmp);
                    tmp = malloc(sizeof(ele->value));
                    strncpy(tmp, ele->value, strlen(ele->value));
                    list_del(&ele->list);
                    free(ele->value), free(ele);
                }
            }
        } else {
            list_del(&ele->list);
            free(ele->value), free(ele);
        }
    }
    if (tmp)
        free(tmp);
    return true;
}

### q_swap
* `li` 為相鄰 node 的第一個 node , `tmp` 則為第二個 node , 並將兩者互換
* 當 `li` 為 `head` 或 `tmp` 為 `head` , 表示已經沒有相鄰的 node 需要互換

void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *li = head->next, *tmp;
    while (li != head) {
        tmp = li->next;
        if (tmp == head)
            break;
        li->prev->next = tmp;
        tmp->next->prev = li;
        li->next = tmp->next;
        tmp->next = li;
        tmp->prev = li->prev;
        li->prev = tmp;
        li = li->next;
    }
}

### q_reverse
* `h` 一開始為第一個節點 , `t` 一開始為最後一個節點
* `h` 一直往後走 , `t` 則一直往前走 , 因為 `h` 跟 `t` 互換 , `h` 要更新為 `t->next` , `t` 則更新為 `h->next`
* 當 `h` 與 `t` 相同或 `t->next->prev` 與 `t` 相同 , linked list 已反轉完畢

void q_reverse(struct list_head *head)
{
    struct list_head *tmp, *htmp, *ttmp;
    if (!head || list_is_singular(head))
        return;
    struct list_head *h = head->next, *t = head->prev;
    head->next = t;
    head->prev = h;
    while (h != t) {
        htmp = h->next;
        ttmp = t->prev;
        tmp = h->next;
        h->next = h->prev;
        h->prev = tmp;
        tmp = t->next;
        t->next = t->prev;
        t->prev = tmp;
        if (t->next->prev == t)
            break;
        h = htmp, t = ttmp;
    }
    if (h == t) {
        tmp = h->prev;
        h->prev = h->next;
        h->next = tmp;
    }
}

* 原本以為 `trace-17-complexity` 有時會沒 pass 的原因只跟 q_insert_tail, q_insert_head, q_remove_tail, q_remove_head 有關 , 後來發現原來是我 q_reverse 寫錯了 , `t->prev` 是 `t->next` 才對 , 而 `tmp` 的宣告也是多餘的
* 不過上面那個錯的 `reverse` 還是能成功將 reverse 後的 linke list show 出來 , 儘管前半段 linked list 節點的 `prev` 應該都是錯的
* 後來推上 github `trace-17-complexity` 還是沒過 , 在本地端測試確實有時不會過 , 還要在看看是那出了問題

void q_reverse(struct list_head *head)
{
    struct list_head *htmp, *ttmp;
    if (!head || list_is_singular(head))
        return;
    struct list_head *h = head->next, *t = head->prev;
    head->next = t;
    head->prev = h;
    while (h != t) {
        htmp = h->next;
        ttmp = t->prev;
        h->next = h->prev;
        h->prev = htmp;
        t->prev = t->next;
        t->next = ttmp;
        if (t->next->prev == t)
            break;
        h = htmp, t = ttmp;
    }
    if (h == t) {
        htmp = h->prev;
        h->prev = h->next;
        h->next = htmp;
    }
}

### q_sort
* 參考 [geekforgeek](https://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/) 實作出適用於 Circular Doubly Linked List 的遞迴法（Top-down） Merge Sort
* 在 Test performance 無法 pass , 在 `qtest` 跑 `trace-14-perf.cmd` 的測資 ， 發現會 Segmetation Fault
* 自己測試後發現 , list 的 size 在約 1400000 就會 Segmetation Fault , 應該是 function 遞迴太多次的關係 , 所以下面改用迭代法（Bottom-up）實作

struct list_head *merge(struct list_head *first, struct list_head *second)
{
    if (!first)
        return second;
    if (!second)
        return first;
    element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list);
    // elef->value < eles->value
    if(strcmp(elef->value,eles->value) < 0)
    {
        first->next = merge(first->next,second);
        first->next->prev = first;
        first->prev = NULL;
        return first;
    }
    else // elef->value >= eles->value
    {
        second->next = merge(first,second->next);
        second->next->prev = second;
        second->prev = NULL;
        return second;
    }
}
struct list_head *split(struct list_head *head)
{
    struct list_head *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct list_head *temp = slow->next;
    slow->next = NULL;
    return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }
    struct list_head *second = split(head);
    head = mergeSort(head);
    second = mergeSort(second);
    return merge(head, second);
}

* 改用迭代法（Bottom-up）實作
* 在 Test performance 還是無法 pass , 在 qtest 跑 trace-14-perf.cmd 的測資 ， 雖然解決了 Segmentation Fault 的問題 卻產生了 time limit exceeded
* 因為 linked list 記憶體並不連續 , 無法像陣列那樣直接取得某個位置的值 , 而必須慢慢往後走 , 導致當要 merge 兩個子 list 前會產生許多很長的走訪
* 所以我沿用原本的遞迴 merge sort ， 但將 merge 的過程改為迭代

void merge_iterative(struct list_head *first, struct list_head *second, int
ls, int rs) {
    int l = 0, r = 0;
    element_t *elef = list_entry(first,element_t,list), *eles = list_entry(second,element_t,list); while(l < ls && r < rs) {
        if(strcmp(elef->value,eles->value) < 0)
        {
            first = first->next;
            l++;
            if(l < ls)
                elef = list_entry(first,element_t,list);
        }
        else // elef->value >= eles->value
        {
            struct list_head *tmp = second->next;
            list_del(second);
            list_add_tail(second,first);
            second = tmp;
            r++;
            if(r < rs)
                eles = list_entry(second,element_t,list);
        }
    }
}

void mergeSort_iterative(struct list_head *head,int size)
{
    int sz = 1,n = size;
    while(sz < n) {
        struct list_head *f = head->next,*s = head->next, *nf = f, *ns;
        int i = 0;
        int j;
        for(j = 0; j < sz; j++)
            s = s->next;
        ns = s;
        while(i < n-1) {
            if(size - i <= sz)
                break;
            int l = sz, r = sz;
            if(n-i-sz < sz)
                r = n-i-sz;
            for(j = 0; j < sz*2; j++) {
                if(nf->next)
                    nf = nf->next;
                if(ns->next)
                    ns = ns->next;
            }
            merge_iterative(f,s,l,r);
            f = nf;
            s = ns;
            i += sz*2;
        }
        sz += sz;
    }
}

* 將 merge 改為迭代的遞迴 mergesort , 總算通過 Test performance
* merge 用來將兩個子 list 合併 , 回傳合併後的head
* split 將 list 切半為兩個子 list

struct list_head *merge(struct list_head *first, struct list_head *second)
{
    if (!first)
        return second;
    if (!second)
        return first;
    struct list_head *tmphead = NULL, *tf = first, *ts = second;
    element_t *elef = list_entry(first, element_t, list),
              *eles = list_entry(second, element_t, list);
    while (first && second) {
        if (strcmp(elef->value, eles->value) < 0) {
            if (!tmphead)
                tmphead = first;
            tf = first;
            first = first->next;
            if (first)
                elef = list_entry(first, element_t, list);
        } else  // elef->value >= eles->value
        {
            if (!tmphead)
                tmphead = second;
            struct list_head *tmp = second->next;
            struct list_head *next = second->next;
            struct list_head *prev = second->prev;
            if (next)
                next->prev = prev;
            if (prev->next == second)
                prev->next = next;
            prev = first->prev;
            if (prev->next == first)
                prev->next = second;
            if (second->next)
                second->next = first;
            second->prev = prev;
            first->prev = second;
            ts = second;
            second = tmp;
            if (second)
                eles = list_entry(second, element_t, list);
        }
    }
    if (first) {
        ts->next = first;
        first->prev = ts;
    }
    if (second) {
        tf->next = second;
        second->prev = tf;
    }
    return tmphead;
}
struct list_head *split(struct list_head *head)
{
    struct list_head *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    struct list_head *temp = slow->next;
    slow->next = NULL;
    return temp;
}
struct list_head *mergeSort(struct list_head *head)
{
    if (!head || !head->next) {
        return head;
    }
    struct list_head *second = split(head);
    head = mergeSort(head);
    second = mergeSort(second);
    return merge(head, second);
}

* 將 linked list 最後一個節點的 `next` 改為 null , 在 `split` 時才不會又跑回最前面
* 做完 merge sort 要更改 `head` 的 `prev` 、 最後一個節點的 `next` 及第一個節點的 `prev`

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = mergeSort(head->next);
    struct list_head *li = head;
    while (li->next) {
        li = li->next;
    }
    head->prev = li;
    head->prev->next = head;
    head->next->prev = head;
}

* 參考 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 中的 `mergeTwoLists` , 透過指標的指標實做 `merge` 函式 , 簡化程式碼
* 用這方式 merge 完後的 linked list `prev` 指標並不會被修改 , 必須在 `mergeSort` 後把它改回來

struct list_head *merge(struct list_head *first, struct list_head *second)
{ 
    struct list_head *head = NULL, **ptr = &head, **node;
    for(node = NULL; first && second; *node = (*node)->next) {
        element_t *elef = list_entry(first, element_t, list), *eles = list_entry(second, element_t, list); 
        node = (strcmp(elef->value, eles->value) <= 0) ? &first : &second;
        *ptr = *node; 
        ptr = &(*ptr)->next;
    }
    *ptr = (struct list_head *)((uintptr_t) first | (uintptr_t) second);
    return head;
}
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = mergeSort(head->next);
    struct list_head *fix_prev ,*li = head;
    while (li->next) {
        fix_prev = li;
        li = li->next;
        li->prev = fix_prev;
    }
    head->prev = li;
    head->prev->next = head;
}

## Linux list_sort

### 引入 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 到 lab0-c
* 將 linux listsort 程式碼拿到 `queue.c` 中
* 宣告用來比較 queue 每個 `entry` 的字串大小的 compare 函式

int list_val_cmp(void *priv, const struct list_head *a, const struct list_head *b) 
{
    element_t *elea = list_entry(a,element_t,list), *eleb = list_entry(b,element_t,list);
    // elea->value <= eleb->value return <= 0
    // elea->value > eleb->value return > 0
    return strcmp(elea->value,eleb->value);
} 
void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    list_sort(NULL,head,list_val_cmp);
}

### 比較自己實做的 Merge Sort 和 Linux 核心程式碼之間效能落差
沿用 `trace-14-perf.cmd` 的測資 , 並透過 `qtest` 所提供的 `time` 命令來測量排序時間

option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
reverse
time
sort
time

| 排序函式 | 執行時間 |
| --- | --- |
| My MergeSort | 0.95s |
| Linux MergeSort | 0.55s |
## 在 qtest 提供新的命令 shuffle

### 在 qtest.c 加上 shuffle 指令
* 在 `console_init` 新增 shuffle 指令
* `ADD_COMMAND` 是定義在 `console.h` 的巨集 `#define ADD_COMMAND(cmd, msg) add_cmd(#cmd, do_##cmd, msg)` , 也是為什麼當我們想新增一個指令 `cmd` , 對應的 function 一定要是 `do_cmd`

ADD_COMMAND(shuffle, "                | Do Fisher–Yates shuffle in queue");

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    if (!l_meta.l)
        report(3, "Warning: Try to access null queue");
    error_check();
    set_noallocate_mode(true);
    if (exception_setup(true)) 
        shuffle(l_meta.l);
    exception_cancel();
    set_noallocate_mode(false);
    show_queue(3);
    return !error_check();
}

### 實做 Fisher–Yates shuffle
* Fisher–Yates shuffle
1. 有一長度為 len 的 list , 設 i 初始為 len
2. 每次隨機取一數 j , 0 <= j <= i
3. 將第 j 個節點與第 i 個節點互換 , 並將 i - 1
4. 重複步驟 2 、 3 直到 i = 1
* `shuffle_point` 為當前要調換位置的節點 , `next_shuffle_point` 為下一個要調換的節點
* 當要互換的節點是同一個節點 , 不做任何事
* 當要互換的節點相鄰 , 移除第一個節點並接在第二個之後
* 其餘的情況 , 先移除第一個節點並接在第二個之後 , 再移除第二個節點並接在原本第一個節點的 `prev` 之後
* `next_shuffle_point` 在互換節點相鄰時 , 節點互換後這時`shuffle_point` 即為下次的 `shuffle_point` , 所以 `next_shuffle_point` 要改為 `shuffle_point->prev`

void shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    int len = q_size(head), x, it;
    struct list_head *li, *shuffle_point = head->prev, *tmp, *next_shuffle_point = shuffle_point->prev;
    while(len-- > 1) {
        li = head->next, it = 0, x = rand() % len;
        while (it++ < x) {
            li = li->next;
        }
        if(li == shuffle_point);
        else if(li->next == shuffle_point) {
            list_del(li);
            list_add(li,shuffle_point);
        }
        else {
            tmp = li->prev;
            list_del(li);
            list_add(li,shuffle_point);
            list_del(shuffle_point);
            list_add(shuffle_point, tmp);
        }
        if(next_shuffle_point != shuffle_point) {
            shuffle_point = next_shuffle_point;
            next_shuffle_point = next_shuffle_point->prev;
            next_shuffle_point = shuffle_point->prev;
        }
        else {
            next_shuffle_point = shuffle_point->prev;
        }
    }
}

## 運用 Valgrind 排除 qtest 實作的記憶體錯誤
透過 make valgrind 可以看到以下訊息 , 這裡取 `trace-01-ops` 產生的訊息來看 , 看起來像是有記憶體沒有釋放

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
==19148== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x4A4D50E: strdup (strdup.c:42)
==19148==    by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
==19148== 137 bytes in 19 blocks are still reachable in loss record 2 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x4A4D50E: strdup (strdup.c:42)
==19148==    by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
==19148== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==19148==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19148==    by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19148==    by 0x111798: linenoiseHistoryLoad (linenoise.c:1329)
==19148==    by 0x10C861: main (qtest.c:1016)
==19148== 
---	trace-01-ops	5/5

`qtest.c`

linenoiseHistoryLoad(HISTORY_FILE); /* Load the history at startup */

`linenoise.c`

int linenoiseHistoryAdd(const char *line)
{
    char *linecopy;

    if (history_max_len == 0)
        return 0;

    /* Initialization on first call. */
    if (history == NULL) {
        history = malloc(sizeof(char *) * history_max_len);
        if (history == NULL)
            return 0;
        memset(history, 0, (sizeof(char *) * history_max_len));
    }

    /* Don't add duplicated lines. */
    if (history_len && !strcmp(history[history_len - 1], line))
        return 0;

    /* Add an heap allocated copy of the line in the history.
     * If we reached the max length, remove the older line. */
    linecopy = strdup(line);
    if (!linecopy)
        return 0;
    if (history_len == history_max_len) {
        free(history[0]);
        memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
        history_len--;
    }
    history[history_len] = linecopy;
    history_len++;
    return 1;
}
int linenoiseHistoryLoad(const char *filename)
{
    FILE *fp = fopen(filename, "r");
    char buf[LINENOISE_MAX_LINE];

    if (fp == NULL)
        return -1;

    while (fgets(buf, LINENOISE_MAX_LINE, fp) != NULL) {
        char *p;

        p = strchr(buf, '\r');
        if (!p)
            p = strchr(buf, '\n');
        if (p)
            *p = '\0';
        linenoiseHistoryAdd(buf);
    }
    fclose(fp);
    return 0;
}

* 一開始以為是 `linenoiseHistoryAdd` 的 `linecopy` 沒有釋放 , 因為他透過 `strdup` 配置記憶體卻沒釋放 , 便嘗試在函式結束前將它釋放 , 結果訊息卻便多了

+++ TESTING trace trace-01-ops:
==19917== Invalid read of size 1
==19917==    at 0x483FED4: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Address 0x4ba1ed0 is 0 bytes inside a block of size 5 free'd
==19917==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Block was alloc'd at
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x4A4D50E: strdup (strdup.c:42)
==19917==    by 0x110C05: linenoiseHistoryAdd (linenoise.c:1240)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
==19917== Invalid read of size 1
==19917==    at 0x483FEE8: strcmp (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110B6D: linenoiseHistoryAdd (linenoise.c:1235)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Address 0x4ba21f1 is 1 bytes inside a block of size 14 free'd
==19917==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110C29: linenoiseHistoryAdd (linenoise.c:1249)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917==  Block was alloc'd at
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x4A4D50E: strdup (strdup.c:42)
==19917==    by 0x110B79: linenoiseHistoryAdd (linenoise.c:1240)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
# Test of insert_head and remove_head
==19917== 160 bytes in 1 blocks are still reachable in loss record 1 of 1
==19917==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==19917==    by 0x110BC5: linenoiseHistoryAdd (linenoise.c:1228)
==19917==    by 0x1117A0: linenoiseHistoryLoad (linenoise.c:1330)
==19917==    by 0x10C861: main (qtest.c:1016)
==19917== 
---	trace-01-ops	0/5

* 決定先看看 `linenoiseHistoryLoad(HISTORY_FILE)` 的 `HISTORY_FILE` 是什麼 , 發現原來是紀錄 `qtest cmd` 曾打過的指令紀錄 `.cmd_history` , 而這些紀錄會記在 `**history` 這個類似字串陣列裡頭
* 所以嘗試把這個 `histroy` 給釋放 , 寫了一個freeHistory 的函式來完成 , 卻發現 `linenoise.c` 原本就有定義這個函式了
* 最後 , 在 `linenoise.c` 裡寫一個函式 `freelinenoise` 來呼叫釋放 histroy 記憶體的函式 `linenoiseAtExit` , 並在 `qtest` 主程式結束前呼叫它 , 成功解決 memory leak 的問題

void freelinenoise() {
    linenoiseAtExit();
}