---
# System prepended metadata

title: 2020q1 Homework1 (lab0)
tags: [進階電腦系統應用2020, lab0]

---

# 2020q1 Homework1 (lab0)
contributed by < `Tim096` >

## Outline
[TOC]

## 環境
- [x] [GNU/Linux 開發工具](https://reurl.cc/KjXbQq)
- [x] [Cppcheck](https://reurl.cc/2g8Zm6): 靜態程式碼分析工具
- [x] [VS-code(安裝C++的套件)，並且用終端機執行](https://reurl.cc/ldZoe9)這邊同步的部分教的不清楚
- [x] [Vim](https://reurl.cc/MdX0Np):終端機，Vim 設定
- [ ] [Valgrind](https://valgrind.org/): 動態程式分析工具
- [x] [Git 教學和 GitHub 設定指引](/@sysprog/git-with-github)
- [x] [HackMD -- LaTeX 語法與示範](/@sysprog/B1RwlM85Z?type=view)
- [ ] [Makefile 語法和示範](/@sysprog/SySTMXPvl?type=view)
- [ ] [Linux製圖工具:gnuplot](https://reurl.cc/ldZoDY)

## 作業事前準備
- [x] 良好的心態
- [x] lab0-c (當中有包含評分系統了)


## 作業要求
- [x] <font color="#f00">Q : circular linked list "" single linked list "" double linked list ? </font>

    A : 老師說要靠自己去發掘(也是一種訓練)
    
在 ``queue.[c/h]`` 中完成以下實作

* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
- [x] <font color="#f00">Q : LIFO準則?Queue正常地從頭前面加入不是FIFO嗎 ? </font>

    A : CMD的文件是這樣寫的，但是其實有點問題
* `q_insert_tail`: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
- [x] <font color="#f00">Q : 相對誰來說 ?</font>

    A : CMD的文件是這樣寫的，但是其實有點問題
* `q_remove_head`: 在佇列開頭 (head) 移除 (remove) 給定的元素。
* `q_size`: 計算佇列中的元素數量。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
* `q_sort`: 以==遞增順序==來排序鏈結串列的元素

## 實作流程 (好好看老師的文件)

### queue.h (以下想法參考別人的) 作者:[ZhuMon](https://hackmd.io/@ZhuMon/lab0-c)

* 更改 `queue.h` 中的 `queue_t` ，使得 `q_size()` 以及 `q_insert_tail()` 能以 $O(1)$ 時間完成
* 依照作業教學，將 `queue.h` 中的 `queue_t` 增加成員 (`size`)
* 此舉能讓 `q_size()` 藉由直接讀取 `queue_t` 中的 `size`，不必每次重新計算 queue 的大小
- [x]      <font color="#f00">空間去換取時間</font>
* 缺點是必須在每次讓 queue 新增或刪除成員時，管理 queue 的 size 以及 `tail` 指標，也讓 queue 所需的記憶體空間增大 `sizeof(pointer) + sizeof(int)`
- [x]      <font color="#f00">這樣用平攤分析 Amortized Analysis的方法算出來的 Time Complexity不就相同了嗎? 而且還是會浪費另外的記憶體空間</font>
    * 這裡只是提供一種方法並不代表是一定就好的


```cpp=
/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;         /* Size of queue */
} queue_t;
```

### queue.c
* **q_new** 
    * 在初始化 `queue_t` 前，先確認是否成功分配記憶體，避免操作到空指標
- [x] <font color="#f00">Q : malloc不是分配記憶體給他嗎? 為何這邊是說確認是否成功分配記憶體 ?</font>

    A : 這邊是指第4行，不是第3行

    ```cpp=
    queue_t *q_new()
    {
        queue_t *q = malloc(sizeof(queue_t));
        if (q) {
            q->head = NULL;
            q->tail = NULL;
            q->size = 0;
        }
        return q;
    }
    ```
    
* **q_free**
    * 新增 `tmp` 作為釋放用的節點
    * 藉由 `q->head` 的移動，遍歷整個 `queue`，並一一清除
    > 本來想以 `q->head` 與 `q->tail` 是否相同作為結束迴圈的條件，後來發現這樣無法完全將 `queue` 清除，於是改為判斷 `q->head` 與 `q->tail`是否同時存在，且發現只要判斷 `q->head` 是否存在即可
    ```cpp=
    void q_free(queue_t *q)
    {
        if (!q)            //如果是空就直接回傳即可
            return;

        list_ele_t *tmp = q->head;
        while (q->head) {
            q->head = q->head->next;
            tmp->next = NULL;
            free(tmp->value);
            free(tmp);
            tmp = q->head;
        }
        free(q);
    }
    ```
- [ ] <font color="#f00">
- [x] Q : 第10行不懂為何要free value，node free掉就好了不就好?</font>
      A : 對，沒有必要
    > 確定沒有必要嗎XD，`tmp->value` 是一個 string 喔~
    > [name=ZhuMon]
    
* **q_insert_head**
    * 將新元素 (`list_ele_t`) 放入 queue 的前端
    * 先判斷傳入的 `q` 是否為 `NULL`，避免分配記憶體後才發現 `q` 為 `NULL`，造成 memory leak
    * 在分配記憶體給新的元素後，判斷是否分配成功，若失敗，則將之前分配的 `newh` 清除
    * 以 C library <`string.h`> 的 `strncpy` 複製 `s`，放入新元素的 `value`
    * 因為 `strncpy` 不會自動將其他位置設為 `\0`，所以使用 `memset` 將 `newh->value` 歸零
    * 確保 `q->tail` 能夠正常運作，第一個 element 建立時，將 `q->tail` 指向 `q->head`，且隨著新增元素，位移到最後
    ```cpp=
    bool q_insert_head(queue_t *q, char *s)
    {
       if (!q)
            return false;

        // Check separately to avoid extra malloc cause memory leak
        
        list_ele_t *newh;  // newh means new element in head
        newh = malloc(sizeof(list_ele_t));
        if (!newh) {
            return false;
        }

        // Allocate space and copy the string
        newh->value = malloc(sizeof(char) * (strlen(s) + 1));
        if (!newh->value) {
            free(newh);
            return false;
        }
        memset(newh->value, '\0', strlen(s) + 1);
        strncpy(newh->value, s, strlen(s));

        newh->next = q->head;
        q->head = newh;

        // first time
        if (!q->tail) {
            q->tail = q->head;
        } else {
            while (q->tail->next) {
                q->tail = q->tail->next;
            }
        }

        q->size += 1;
        return true; 
    }

    ```
- [ ] <font color="#f00">Q : 第15行的 `* (strlen(s) + 1));` 這一部分不曉得為何需要 ? </font>

    A : 新版的CPP99其實已經不需要這樣了
    
- [ ] <font color="#f00">Q : 第16~18行如此判斷如果傳入Value=0是否會判斷錯誤 </font>

    A : 
    
- [ ] <font color="#f00">Q : 第20~21行為何不直接使用strcpy代替呢 ?  </font>

    A : 
    

* **q_insert_tail** 
    * 與 `q_insert_head` 差不多
    * 將新元素 (`list_ele_t`) 放入 queue 的尾端
    * 若 `queue` 為空 (`q->tail == NULL`)，則將 `head` 和 `tail` 同時指向新元素 (`newt`)
    ```cpp=
    bool q_insert_tail(queue_t *q, char *s)
    {
        if (!q)
            return false;

        // Check separately to avoid extra malloc cause memory leak
        list_ele_t *newt;  // newt means new element in tail
        newt = malloc(sizeof(list_ele_t));
        if (!newt)
            return false;

        newt->value = malloc(sizeof(char) * strlen(s) + 1);
        if (!newt->value) {
            free(newt);
            return false;
        }
        memset(newt->value, '\0', strlen(s) + 1);
        strncpy(newt->value, s, strlen(s));
        newt->next = NULL;
        if (!q->tail) {
            q->tail = q->head = newt;
        } else {
            q->tail->next = newt;
            q->tail = newt;
        }

        q->size += 1;
        return true;
    }
    ```
* **q_remove_head**
- [ ] <font color="#f00">Q : 為何要傳入這麼多的參數，不是只要remove掉head這個東西嗎 ? </font>
    A : 
    
    * 藉由確認 `q->head` 是否為 `NULL`，確認 `queue` 是否為空
    * 若 `sp` 不為 `NULL`，必須將成功刪除後的字串複製進去，並且依照傳入的 `bufsize` 決定複製多少
        * 比較 `bufsize` or 要刪除的字串長度 比較短，來決定真正要複製進 `sp` 的長度為何
        * 呼叫 `memset` 時，需要保留最後一位來放 `\0`，所以 `realbufsize` 要加一 
        ```cpp
        memset(sp, '\0', realbufsize + 1)
        ```
        * 若只複製部分字串(`bufsize`)，由於呼叫 `memset` 會將 size += 1，而且複製完不能超過 `bufsize`，所以 `realbufsize = bufsize - 1`
    * 新增一個指標 `tmp` 以供釋放 (`free`) 
    * 將 `tmp` 的成員都清空後，再釋放 `tmp`
    ```cpp=
    bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
    {
        if (!q || !q->head) {
            return false;
        }
        if (sp) {
             // Insure copy size is right
            size_t realbufsize = (bufsize > strlen(q->head->value))
                                 ? strlen(q->head->value)
                                 : bufsize - 1;
            memset(sp, '\0', realbufsize + 1);
            strncpy(sp, q->head->value, realbufsize);
        }
        
        list_ele_t *tmp;
        
        tmp = q->head;
        q->head = q->head->next;
        tmp->next = NULL;
        free(tmp->value);
        free(tmp);

        q->size -= 1;
        return true;
    }
    ```

* **q_size**
    * 若 `q` 不存在，則返回 `0`
    * 藉由直接取得 `q->size`，達成在 $O(1)$ 時間內完成 `q_size()`
    * 在 `q_new` 時，便已將 `q->size` 設為 `0` ，因此就算 queue 為空，還是會返回 `0`
    ```cpp
    int q_size(queue_t *q)
    {
        return !q ? 0 : q->size;
    }
    ```

* **q_reverse** 
    * 原本使用三個指標 (`prev`, `now`, `next`) 來反轉 queue
    * 一直思考如何將指標數量縮減，借鑑 [gpwork4u 的方式](https://hackmd.io/@gpwork4u/2020q1-hw-lab0c)後，發現可以藉由暫時不會用到的指標：`q->tail->next` 和 `q->head->next`，取代新的指標，只使用一個新的指標 `tmp`
    * 藉由檢查 `q->size < 2` 來確認 `queue` 是否只有一個或沒有元素
        * <font color="#f00">此處的部份我不曉得先暫時多用一個只會會有何影響？因此我認為程式碼的易讀性更重要，因此我寫了一個Part2的版本</font>


    ```cpp=
    void q_reverse(queue_t *q)
    {
        // No effect if q is NULL or empty or only one element
        if (!q || q->size < 2) {
            return;
        }

        list_ele_t *tmp;
        tmp = q->head->next;
        q->tail->next = q->head;

        while (tmp != q->tail) {
            tmp = tmp->next;
            q->head->next->next = q->tail->next;
            q->tail->next = q->head->next;
            q->head->next = tmp;
        }
        q->tail = q->head;
        q->head = q->head->next;
        q->tail->next = NULL;
    }
    ```
- [ ] <font color="#f00">Q : 第4行`if (!q || q->size < 2)`中的`!q`是多餘的吧 ? (一開始即有定義 init=0)</font>
    A : 

    * 下圖為進入 while 迴圈之前，queue 的狀況，分別用三種顏色（紫、綠、紅）代表主要控制的指標

    ```graphviz
    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <ref>  }"];
        b [label="{ <data> b | <ref>  }"];
        c [label="{ <data> c | <ref>  }"];
        d [label="{ <data> d | <ref>  }"];
        a:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false, color="red"];
        b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false];
        c:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false];
        d:ref:d -> a:data [arrowtail=dot, dir=both, tailclip=false, color="green"]
        head -> a;
        tmp ->b [color="purple"];
        tail -> d;
    }
    ```
    1. 進入迴圈後，先將 `tmp` 指向下一個，避免待會將 `b->next` 反向後，無法取得 `c`
    2. 接著藉由操作 `q->head->next->next`，將 `b->next` 反向，指向 `a`
    3. 為了讓 `q->head->next` 前進，而不至於讓 `b` 無法取得，於是將 `tail->next` 指向 `b`
    4. 將 `q->head->next` 指向 `tmp`，準備下次的反向
    <pre>
    while (tmp != q->tail) {
        <span style="color:purple">tmp = tmp->next;</span>
        <span style="color:blue">q->head->next->next = q->tail->next;</span>
        <span style="color:green">q->tail->next = q->head->next;</span>
        <span style="color:red">q->head->next = tmp;</span>
    }
    </pre>

    ```graphviz
    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <ref>  }"];
        b [label="{ <data> b | <ref>  }"];
        c [label="{ <data> c | <ref>  }"];
        d [label="{ <data> d | <ref>  }"];
        a:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false, color="red", style="invis"];
        a:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false, color="red"];
        b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false, style="invis"];
        b:ref:c -> a:data [arrowtail=dot, dir=both, tailclip=false, color="blue"]
        c:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false];
        d:ref:d -> b:data [arrowtail=dot, dir=both, tailclip=false, color="green", label=""]
        head -> a;
        tmp -> c [color="purple"];
        tail -> d;
    }
    ```

    <pre>
    while (tmp != q->tail) {
        <span style="color:purple">tmp = tmp->next;</span>
        <span style="color:blue">q->head->next->next = q->tail->next;</span>
        <span style="color:green">q->tail->next = q->head->next;</span>
        <span style="color:red">q->head->next = tmp;</span>
    }
    </pre>

    ```graphviz
    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        a [label="{ <data> a | <ref>  }"];
        b [label="{ <data> b | <ref>  }"];
        c [label="{ <data> c | <ref>  }"];
        d [label="{ <data> d | <ref>  }"];
        a:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false, color="red", style="invis"];
        a:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false, color="red"];
        b:ref:c -> c:data [arrowtail=dot, dir=both, tailclip=false, style="invis"];
        b:ref:c -> a:data [arrowtail=dot, dir=both, tailclip=false]
        c:ref:c -> d:data [arrowtail=dot, dir=both, tailclip=false, style=invis];
        c:ref:c -> b:data [arrowtail=dot, dir=both, tailclip=false, color="blue"];
        d:ref:d -> c:data [arrowtail=dot, dir=both, tailclip=false, color="green"]
        head -> a;
        tmp -> d [color="purple"];
        tail -> d;
    }
    ```



:::warning
考慮以下變更:
```diff
@@ -1,14 +1,13 @@
 void q_reverse(queue_t *q)
 {
-    if (q == NULL || q->head == NULL) {
+    if (!q  || !q->head)
         return;
-    }
+
     list_ele_t *prev, *now, *next;
     prev = q->head;
     now = q->head->next;
-    if (now == NULL) {  // there is only one element in queue
+    if (!now) /* only one element in queue */
         return;
-    }
 
     next = q->head->next->next;
 
@@ -18,7 +17,7 @@
 
     prev->next = NULL;
     now->next = prev;
-    while (next != NULL) {
+    while (next) {
         prev = now;
         now = next;
         next = now->next;
```

要點: 維持簡潔的縮排和風格
:notes: jserv
:::


:::success
已更改程式碼為只剩一個新指標
:::


* **q_reverse_Part2**

```cpp=
void q_reverse(queue_t *q){

    if (q->size < 2) {
        return;
    }

    list_ele_t *pre = 0,
               *tmp = head,
               *next = head->next;

    while (next != 0) {
        tmp->next = pre;      
        pre = tmp;            // pre往後挪
        tmp = next;           // tmp往後挪
        next = next->next;   // next往後挪
    }                                  // next更新成NULL即跳出while loop

    tmp->next = pre;          // 此時tmp位於最後一個node, 將tmp->next轉向
    head = tmp;                   // 更新head為tmp
}

```


* **q_sort**
    * 參考 [Linked LIst Sort](https://npes87184.github.io/2015-09-12-linkedListSort/)
    * 使用 Merge sort 排序
    * `merge_sort()`
        * 將一個 Linked list 拆成兩個
            * 藉由兩個指標 (`l1`, `l2`) 不同速度的前進 
            * `l1` 會指向最後的 `element`
            * `l2` 會指向中間的 `element`
            * 將 `l1` 指向 `l2->next` 後，便可以得到兩個等長的 `linked list` (`head` 和 `l1`)
            * 將 `l2` 指向 `*head`，避免接下來使用 `*head` 後造成錯誤
        * 將兩個已排序的 Linked list 合成一個 Linked list，並回傳
            * 參考 [jwang0306](https://hackmd.io/@jwang0306/lab0-c) 的 `merge`，將比較字串的部分縮進 `while`
            * 藉由走訪 `l1` 和 `l2`，並比較兩者元素，來建立新 Linked list
            * 最後離開 `while` 不是剩下 `l1` 就是 `l2`，於是縮成一行
    * `q_sort()`
        * 藉由 pointer to pointer 省略回傳 `q->head`
    ```cpp
    void merge_sort(**head)
    {
        if (!(*head) || !((*head)->next))
            return;

        list_ele_t *l1 = (*head)->next;  
        list_ele_t *l2 = *head;          

        while (l1 && l1->next) {
            l2 = l2->next;
            l1 = l1->next->next;
        }
        l1 = l2->next;
        l2->next = NULL;
        l2 = *head;

        merge_sort(&l2);
        merge_sort(&l1);

        *head = NULL;
        list_ele_t **tmp = head;

        while (l1 && l2) {
            if (strcmp(l1->value, l2->value) < 0) {  
                *tmp = l1;
                l1 = l1->next;
            } else {
                *tmp = l2;
                l2 = l2->next;
            }
            tmp = &((*tmp)->next);
        }

        *tmp = l1 ? l1 : l2;
    }

    void q_sort(queue_t *q)
    {
        // if q has only one element or q is empty, q->head == q->tail
        if (!q || q->head == q->tail) {
            return;
        }

        merge_sort(&q->head);

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

    :::warning
    TODO:
    1. 考量到程式碼變數和函式命名的風格 (作業說明有提及，採用 Linux 核心程式碼慣用風格)，請修改上述程式碼，用小寫和精準的用字;
    2. 程式碼尚可更精簡，請改寫;
    :notes: jserv
    :::
    
    :::info
    1. 沒有注意到參考的程式碼與當前的命名風格不同，已改正
    2. 改寫程式碼
       * 將原來的 `merge()` 以及 `mergeSortList()` 合併為 `merge_sort()`
       * ~~想將比較字串部分都縮進 `while` 迴圈內，但是還想不到辦法實現~~
       * ~~雖然暫時無法再縮減程式碼~~，但是比較字串的 branch 數似乎也無法再降低
       
        (更新）
        * 參考 [jwang0306](https://hackmd.io/@jwang0306/lab0-c) 藉由 pointer to pointer 將比較字串的部分縮進 `while` 
        * 使用 pointer to pointer 省略回傳值
        * 將使用的變數量縮減（重複使用變數）
        * 在 hackmd 上刪除部分註解，避免雜亂
    :::
    
    <font color="#f00">以上讀完但有問題</font>
    
    <font color="#f00">以下通通都還沒有讀完</font>
    -------------
    
### natsort
* 參考 [natsort](https://github.com/sourcefrog/natsort)，將 `strcmp` 改為 `strnatcmp`
    > 發現在執行 `traces/trace-15-perf.cmd` 時，會因為時間超過，而測試失敗
* 於是確認 `strcmp` 與 `strnatcmp` 的需要時間。以 `time.h` 的 `clock` 函式計算時間
    > 此為未使用任何 gcc 最佳化方法 (-O1 -O2 -O3 ...) 的狀況
    
![](https://i.imgur.com/UBNHceJ.png)
* 發現 `strnatcmp` 需要的時間在十萬次以上的情況下，與 `strcmp` 差距極大，造成 `qtest` Timeout


:::warning
很好！你終於發現這個故意安插的細節。
需要留意到，glibc 裡頭的 strcmp 做了一系列最佳化，類似 [Speeding up string compare and sorting](http://mgronhol.github.io/fast-strcmp/) 的手段，但額外透過 SSE 和 AVX 指令集加速。相反地，[natsort](https://github.com/sourcefrog/natsort) 實作就很 naive (取「原始」和「單純」的意思)，意味著有很大的加速空間，你可試著改進，記得對照 [CS:APP 第 5 章](https://hackmd.io/@sysprog/CSAPP-ch5) 來思考。
:notes: jserv
:::

> 經由老師提示，我試著去 linux kernel 內尋找有使用到 natural sort 的部分，一開始我認爲應該跟 file system 有關，於是聚焦在 [linux/fs](https://github.com/torvalds/linux/tree/master/fs)，粗略地尋找了一陣子卻沒有找到有關的資訊，但是在搜尋的過程中有發現 `sort` 這個命令

:::danger
1. 命令 (command) 和指令 (instruction) 不同，後者在「Linux 核心設計」課程特別指 CPU instruction，因此，`sort` 只能被稱「命令」，請變更用語;
2. Linux 核心的檔案系統主要維護 metadata (反映資料行為的資料)，可參見 `i-node`，`sort` 就仰賴 metadata 進行排序，所以，討論的主體該釐清，不是 Linux 核心去「排序」檔案名稱，而是 coreutils 一類的套件提供 `sort` 工具來排序;

:notes: jserv
:::

> 1. 好的，已更改用語
> 2. 也就是說我一開始的找尋方向錯誤，Linux 核心不負責檔案的排序，「人類」看到的檔案系統順序都是由 coreutils 等套件來排序，所以我的確應該去閱讀 coreutils 的 `sort` 命令

:::warning
不能說「方向錯誤」，有好奇心是值得稱許的事。需要注意，排序不全然跟 Linux 核心無關，可參見 [The kernel and character set encodings](https://lwn.net/Articles/71472/)，在核心內部的檔案系統實作，我們還是需要透過核心處理字元集 (如 Big5 [廣泛用於台灣], GB18030 [中國國家標準])，這樣後續在使用者層級的排序才有意義。
:notes: jserv
:::

* 確認 `sort` 這個命令是否符合 natural sort
    * 發現 string 中含有空白時，兩者的行為會有差異
    * sourcefrog 的 natural sort
        ```
        pic01
        pic2
        pic 4 else
        pic 5
        pic   7
        ```
    * macOS 的 `sort` 命令
        > 後來發現應該使用 `$ sort -V` 來做排序
        ```
        pic   7
        pic 4 else
        pic 5
        pic01
        pic2
        ```
    * 再去各種線上排序的網站實驗後，發現每個網站對於 natural sort 的定義也都不一樣
        > 測試了 [Text Mechanic](https://textmechanic.com/text-tools/basic-text-tools/sort-text-lines/), [PineTools](https://pinetools.com/sort-list), [Gillmeister Software](https://gillmeister-software.com/online-tools/text/sort-list.aspx)
    * 閱讀 `sort` 命令的 man page 後，發現， `sort` 可以針對版本號碼做排序
        ```shell
        $ ls pic* | sort -V
        pic01
        pic2
        pic 4 else
        pic 5
        pic   7
        ```
        效果符合 sourcefrog 的預期
* 稍微閱讀 [`sort` 命令](https://github.com/coreutils/coreutils/blob/master/src/sort.c) 的運行方式後，發現 `sort.c` 關於檔案、版本號碼的排序是由 [filevercmp](https://github.com/gagern/gnulib/blob/master/lib/filevercmp.c) 這個檔案來實作
* 實際與 strcmp、strnatcmp 比較 （開啟 `-O3` ）
![](https://i.imgur.com/rJSTqf9.png)
   很明顯地看到 filevercmp 遠超其他兩者
   > strcmp 所需時間一直只在 1 µs 附近，或許更低，但目前使用的 library 精準度只到微秒
* 另外，我還有發現字串越接近版本號（部分相似），strnatcmp 與 filevercmp 的表現越差
* TODO: 發現 `gnulib` 比較字串的方式效率也不盡人意後，決定先熟悉編譯器的最佳化等教材，之後再試著改進

## Valgrind 實驗
> 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

### 排解使用原配置可能造成的錯誤

* 使用 `make valgrind` 命令後，想要讓使用 `massif` 來視覺化記憶體使用量，可是卻發生錯誤
    ```zsh
    $ valgrind --tool=massif ./qtest
    valgrind: Unknown option: --show-leak-kinds=all
    valgrind: Use --help for more information or consult the user manual.
    ```

* 由於在 macOS 和 Linux 都遇到相同問題，確認兩者的版本
    * macOS 10.14.6
      ```
      $ valgrind --version
      valgrind-3.14.0.GIT
      ```
      :::spoiler
      * 更新 macOS 的 Valgrind
          ```
          $ brew upgrade valgrind
          ```
      * 發生錯誤，要我更新 xcode，於是照著提示更新 xcode
      * 由於之前安裝 Ubuntu 環境一直失敗，以爲是 macOS 版本的問題，於是將系統從 High Sierra(10.13.6) 升級到 Mojave (10.14.6)，所以 valgrind 是之前安裝的
      * 升級完 xcode 後，想升級 Valgrind，發現 Valgrind not Found，試著安裝...
          ```shell
          $ brew install valgrind
          ...
          valgrind: This formula either does not compile or function 
                    as expected on macOS versions newer than High Sierra
                    due to an upstream incompatibility.
          Error: An unsatisfied requirement failed this build.
          ``` 
       * 只好試著以 github 安裝
           參考 [此篇](https://stackoverflow.com/questions/52732036/how-to-install-valgrind-on-macos-mojave10-14-with-homebrew)
        ```
        $ brew install --HEAD https://raw.githubusercontent.com/sowson/valgrind/master/valgrind.rb
        ```
        * 安裝成功，可是版本竟然是 3.16.0 ?
        ```
        $ valgrind --version
        valgrind-3.16.0.GIT
        ```
        * 重新測試，發生同樣問題
        ```
        $ valgrind --tool=massif ./qtest
        valgrind: Unknown option: --show-leak-kinds=all
        valgrind: Use --help for more information or consult the user manual.
        ```
        :::
    * Ubuntu 19.10
      ```
      $ valgrind --version
      valgrind-3.15.0
      ```
  查詢 [Valgrind 官網](http://valgrind.org/downloads/?src=www.discoversdk.com) 發現，最新版本的確是 3.15.0
  
* 重新閱讀 lab0-c 的 `README.md` 後，發現在 `.valgrindrc` 中有關於 Valgrind 的配置，並且找到該選項，將它刪除後，便可運作
* 發現 Valgrind 的另外一個配置： `--leak-check` 在 `.valrindrc` 裡的寫法為 `--memcheck:leak-check=full`，於是將 `--show-leak-kinds=all` 前也加上 `memcheck`，再執行，便通過了
    * before
    ```
    --show-leak-kinds=all
    ```
    * after
    ```
    --memcheck:show-leak-kinds=all
    ```

:::warning
請提交 `.valrindrc` 相關的 pull request
:notes: jserv
:::

:::success
已提交
:::


### 設計實驗
* 目的：    想要知道 strnatcmp 與 filevercmp 的記憶體用量

#### 實驗一
* 讓兩者比較兩個不同字串 100000 次
* ![](https://i.imgur.com/Vzp3EKC.png)
* TODO


## 論文 Dude, is my code constant time?
> 研讀論文 Dude, is my code constant time?，解釋本程式的 “simulation” 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 Student’s t-distribution 及程式實作的原理;

* 簡稱 `dudect`
* TODO

## 獨立的終端機命令解譯器
> 解釋 select 系統呼叫在本程式的使用方式，並分析 console.c 的實作，說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示 :arrow_forward: 為避免「舉燭」，請比照 qtest 實作，撰寫獨立的終端機命令解譯器 (可建立新的 GitHub repository)

### select 系統呼叫
* 在 [Linux manual page](http://man7.org/linux/man-pages/man2/select.2.html) 定義 select 如下
    ```cpp
    /* According to POSIX.1-2001, POSIX.1-2008 */
    #include <sys/select.h>

    /* According to earlier standards */
    #include <sys/time.h>
    #include <sys/types.h>
    #include <unistd.h>

    int select(int nfds, fd_set *readfds, fd_set *writefds,
                  fd_set *exceptfds, struct timeval *timeout);
    ```
* `select()` 可以監聽多個 file descriptors，
* TODO

## Bonus
發現新通過的 Pull request 含有一些小bug，進行修改

* Add description of clang-format integration to vim ([#28](https://github.com/sysprog21/lab0-c/pull/28))
* 簡介：藉由在 vim 中新增 function，使得每次寫進 C/C++ 文件後，自動排版
```shell
function! Formatonsave()
  let l:formatdiff = 1
  py3f <path to your clang-format.py>/clang-format.py
endfunction
autocmd BufWritePre *.h,*.cc,*.cpp call Formatonsave()
```
> 已發 Pull Request，也已通過
> Extend auto-indention for generic C/C++ source ([#29](https://github.com/sysprog21/lab0-c/pull/29))
> 簡介：新增 *.c 以及 *.hpp，使得 C/C++ 的檔案都適用自動排版

由於我的主系統是 macOS，他這個方法需要找到 `clang-format.py` 的位置，再取代 `<path to your clang-format.py>`，避免以後還需要再手動更新，於是寫了一個 script 將路徑寫好，並且 `export` 成環境變數

* .vimrc
    * 將 `clang-format.py` 的位置以 `$CLANG_FORMAT_PATH` 取代
    ```shell
    ...
    function! Formatonsave()
      let l:formatdiff = 1
      py3f $CLANG_FORMAT_PATH
    endfunction
    autocmd BufWrite *.h,*.hpp,*.c,*.cpp,*.c++ call Formatonsave()
    ...
    ```
* [setEnv.sh](https://github.com/ZhuMon/vimrc/blob/master/setEnv.sh)
    * 藉由 `uname` 命令，找出當前是在哪個作業系統
    * 由於我存放 `setEnv.sh` 的資料夾裡，也有複製了老師的 `.clang-fomat` 檔案，所以之後不管在哪裡都會使用該設定進行排版
    * 我是使用 ==zsh==，所以會將設定放到 `~/.zshrc`
    
    ```shell
    #!/bin/sh
    # Set environment of clang-format

    sysOS=`uname`

    if [ $sysOS = "Darwin" ]; then
        echo "On Mac OSX"
        echo "export CLANG_FORMAT_PATH to ~/.zshrc"
        echo "export CLANG_FORMAT_PATH=\"/usr/local/Cellar/clang-format/2019-05-14/share/clang/clang-format.py\"" >> ~/.zshrc
        echo "export clang_format_fallback_style=\"$PWD/.clang-format\"" >> ~/.zshrc

    elif [ $sysOS = "Linux" ]; then
        echo "On Linux"
        echo "export CLANG_FORMAT_PATH to ~/.zshrc"
        echo "export CLANG_FORMAT_PATH=\"/usr/share/vim/addons/syntax/clang-format.py\"" >> ~/.zshrc
        echo "export clang_format_fallback_style=\"$PWD/.clang-format\"" >> ~/.zshrc
    else
        echo "I don't know where clang-format.py is"
    fi
    ```



## 自我檢討
- [ ] natural sort
- [ ] 設計 Valgrind 實驗
- [ ] 讀論文
- [ ] 設計終端機命令解譯器

###### tags: `進階電腦系統應用2020` `lab0`