# 2021q1 Homework1 (lab0)
contributed by <[`xxiex123`](https://github.com/xxiex123/lab0-c)>
###### tags: `linux2021`

## 環境

Linux DESKTOP-KB3JHRC 5.4.72-microsoft-standard-WSL2 #1 SMP Wed Oct 28 23:40:43 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux
gcc version 9.3.0 (Ubuntu 9.3.0-10ubuntu2)

依照 C Programing Lab 的作業標準，額外添加實作queue sorting 的函數

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: 「Linux 核心設計」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;

因在這之前，并沒有使用 app 輔助寫程式碼的習慣，因此在一系列的設置環境后（git、vim、llvm、clang、valgrind 等等），開始實作補上程式碼的部分。

這些函式都非常直觀，只要處理好malloc 與free ，基本上沒什麽太大問題。也沒什麽好講解的，因此直接附上程式碼。

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;
}

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    else if (q->size == 0) {
        free(q);
        return;
    }

    while (q->head) {
        list_ele_t *temp;
        temp = q->head;
        q->head = q->head->next;
        free(temp->value);
        free(temp);
    }
    free(q);
}

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;
    }
    for (int i = 0; i < strlen(s) + 1; i++)
        newh->value[i] = s[i];
    newh->next = q->head;
    if (q->head == NULL)
        q->tail = newh;
    q->head = newh;
    q->size++;
    return true;
}

bool q_insert_tail(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;
    }
    for (int i = 0; i < strlen(s) + 1; i++) {
        newh->value[i] = s[i];
    }
    newh->next = NULL;
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    return true;
}

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0)
        return false;

    list_ele_t *temp = q->head;
    q->head = q->head->next;

    if (sp) {
        if (strlen(temp->value) >= bufsize - 1) {
            for (int i = 0; i < bufsize - 1; i++)
                sp[i] = temp->value[i];
            sp[bufsize - 1] = '\0';
        } else {
            int i;
            for (i = 0; i < strlen(temp->value) + 1; i++)
                sp[i] = temp->value[i];
            sp[i + 1] = '\0';
        }
    }

    free(temp->value);
    free(temp);
    if (q->head == NULL)
        q->tail = NULL;
    q->size--;
    return true;
}

int q_size(queue_t *q)
{
    if (q == NULL) {
        return 0;
    } else
        return q->size;
}

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size <= 1)
        return;

    list_ele_t *tempOne;
    list_ele_t *tempTwo;

    tempOne = q->head->next;
    q->head->next = NULL;
    q->tail = tempTwo = q->head;
    while (tempOne) {
        q->head = tempOne;
        tempOne = tempOne->next;
        q->head->next = tempTwo;
        tempTwo = q->head;
    }
}

這裏的 list-sort 方式是用 merge sort 的演算法。因爲merge sort 算是較容易達到 nlogn 的時間複雜度。

void split(queue_t *q, queue_t *left, queue_t *right)
{
    int middle = q->size / 2 - 1;
    left->head = q->head;
    left->size = middle + 1;
    right->tail = q->tail;
    right->size = q->size - left->size;
    for (int i = 0; i < middle; i++)
        q->head = q->head->next;
    left->tail = q->head;
    right->head = q->head->next;
    left->tail->next = NULL;
}

void merge(queue_t *q, queue_t *left, queue_t *right)
{
    if (strcmp(left->head->value, right->head->value) < 0) {
        q->tail = q->head = left->head;
        left->head = left->head->next;
    } else {
        q->tail = q->head = right->head;
        right->head = right->head->next;
    }

    while (left->head && right->head) {
        if (strcmp(left->head->value, right->head->value) < 0) {
            q->tail->next = left->head;
            q->tail = left->head;
            left->head = left->head->next;
        } else {
            q->tail->next = right->head;
            q->tail = right->head;
            right->head = right->head->next;
        }
    }

    if (right->head) {
        q->tail->next = right->head;
        q->tail = right->tail;
    } else {
        q->tail->next = left->head;
        q->tail = left->tail;
    }
    q->size = left->size + right->size;
}

void mergesort(queue_t *q)
{
    if (q->size <= 1)
        return;

    queue_t left, right;

    split(q, &left, &right);
    mergesort(&left);
    mergesort(&right);
    merge(q, &left, &right);
}

void q_sort(queue_t *q)
{
    if (q == NULL) {
        return;
    } else if (q->size < 2) {
        return;
    }

    mergesort(q);
}

由以上程式碼，進行make test 結果為100
## make valgrind
而進行 make valgrind 時，大家都會出現一個 still reachable 的結果，觀察了錯誤訊息后發現這是從 linenoise.c 裏， malloc 了參數 `history` 而在 qtest 結束執行時卻沒有 free。

觀察了幾個同學的作業后，發現有的同學是直接避免呼叫linenoise 的初始化，我覺得方法不是很好，因爲等於由有部分功能被迫關閉，治標不治本。

因此我在 linenoise 裏加了一個 linenoiseFreeAll 的函數，在 qtest.c 裏準備結束執行時去 free `history` 。

    add_quit_helper(queue_quit);
    // edited for valgrind error
    linenoiseFreeAll();
    

void linenoiseFreeAll()
{
    for (int i = 0; i < history_len; i++)
        free(history[i]);
    free(history);
    return;
}

由此解決 valgrind error。

## AddressSenitizer
由 `make SANITIZER=1`

$ make SANITIZER=1
make: Nothing to be done for 'all'.

AddressSanitizer 好像沒有被激活，通過 make test 也沒有發生大家都會遇到的 segmentation fault 的問題，程式照常執行評分。
於是由 [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) , 發現我沒有clang，而且貌似需要安裝llvm，因此照著 [Installing LLVM](https://www.youtube.com/watch?v=l0LI_7KeFtw) 去安裝 llvm ，其中用
`-DLLVM_ENABLE_PROJECTS="clang,compiler-rt"` 把 compiler-rt 也一起 enable 了。過程中安裝了一整個晚上，結果發現在 llvm-project/build/bin 裏卻還是沒有 clang。
查了一下發現 clang 可以用 `sudo apt-get install clang` 去安裝，但安裝完成后再次用 `make SANITIZER=1` 指令，結果還是一樣沒改變，到了這裏也沒思緒了。

## massif visualizer
因爲本人環境為 WSL(Windows Subsystem for Linux) 因此執行指令 `massif-visualizer` 會有 could not connect to display 的問題

qt.qpa.xcb: could not connect to display
qt.qpa.plugin: Could not load the Qt platform plugin "xcb" in "" even though it was found.

This application failed to start because no Qt platform plugin could be initialized. Reinstalling the application may fix this problem.

嘗試 reinstall

$sudo apt-get install libxcb
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package libcxb

查了一下遇到同樣問題的，大多都是安裝 libcxb 相關的 package 就能解決問題，但我幾乎把全部 libcxb 為開頭名稱的package 都安裝了，還是沒辦法解決，之後發現使用 WSL 需要另外在 windows 上安裝一個類似服務器的東西，然後用 WSL 安裝類似 XFCE4 一樣的桌面環境，再連接上前者，才能提供 WSL 一個可視化的能力（據説 WSL 團隊早已聲名主要為 Command line Developer 服務)。參考文章 [Installing WSL with GUI using VcXsrv](https://medium.com/@dhanar.santika/installing-wsl-with-gui-using-vcxsrv-6f307e96fac0)。

經過一番折騰，終於能夠透過 VcXsrv 與 XFCE4 ，呈現出massif-visualizer 的圖形

由 `massif-visualizer massif.out.<pid>`呈現下圖