# 2025q1 Homework1 (lab0)
contributed by < [kendellhsu](https://github.com/kendellhsu) >

### Reviewed by `rota1001`
1. 看到 github 上有些東西在這裡沒有紀錄，請補上開發紀錄。
2. 不同的功能請分開在不同的 Commit 中。

### Reviewed by `MikazkiHikari`
1. 請確認是否有按照預期進行rebase。
2. 對於 queue.[ch] 實作的部分，若能在共筆中補充你實作的核心邏輯程式碼，並搭配講解將有助於他人更快理解你的思路。
3. 實作的項目好像還有其他的吧?

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          43 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 5 2600 Six-Core Processor
    CPU family:           23
    Model:                8
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             2
    Frequency boost:      enabled
    CPU max MHz:          3400.0000
    CPU min MHz:          1550.0000
    BogoMIPS:             6799.78

## TO DO LIST:
以下複製自「作業要求」

- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [ ] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `$ make test` 自動評分系統的所有項目。
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
* [ ] 研讀 Linux 核心 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 原始程式碼的並引入自己的專案
* [ ] 比較效能落差
- [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制
- [ ] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
- [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作 (可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift))，搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
- [ ] 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。
* [ ] 注意：現有實作存在若干致命缺陷，請討論並提出解決方案
* [ ] 解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution)
* 在 [oreparaz/dudect](https://github.com/oreparaz/dudect) 的程式碼具備 percentile 的處理，但在 [lab0-c](https://github.com/sysprog21/lab0-c) 則無。
- [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
- [ ] 除了修改程式，也要編輯「[作業區](https://hackmd.io/@sysprog/linux2023-homework1)」，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
* [x] 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2023-lab0-a), [(二)](/@sysprog/linux2023-lab0-b), [(三)](/@sysprog/linux2023-lab0-c), [(四)](/@sysprog/linux2023-lab0-d), [(五)](/@sysprog/linux2023-lab0-e)，記錄你的啟發和疑惑
* [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
* [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
* [ ] 解釋 [select](http://man7.org/linux/man-pages/man2/select.2.html) 系統呼叫在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/H1TtmVTTz)

## 開發過程

### `q_new`
新增一個佇列的head

### `q_insert_head`, `q_insert_tail`
#### <1>
由於這個 queue 是 doubly linked looped list ，所以可以透過 head 指標找到 queue 的 head 跟 tail，因此這兩個function中的操作無太大差異，差別只在最後要把節點加入queue時要使用`list_add` 還是 `list_add_tail`

一開始在測試的時候發現會出現 insert error，檢查過後發現 malloc 一個 element_t 之後若要儲存值需要 malloc 記憶體給tmp->value， 程式碼如下

`tmp->value = malloc(sizeof(strlen(s)+1))`

#### <2>
使用 `strdup` 增加程式的易讀性，這個

### q_delete_mid
使用快慢指標的方式，找到queue的中點

#### q_delete_mid
原本想用快慢指標的 但觀摩alanjian85的作業後發現了解到可以善用doubly linked list的特性

#### q_delete_dup
第一次錯誤嘗試 會發生

bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head)
        return false;
    if (list_empty(head) || list_is_singular(head))
        return true;

    bool dup = 0;
    element_t *curr, *next;
    list_for_each_entry_safe(curr, next, head, list){
        bool equal = !strcmp(curr->value,next->value);
        if (equal || dup){
            list_del(&curr->list);
            q_release_element(curr);
            dup = equal;
        }
    }

    if(dup){
        list_del(&curr->list);
        q_release_element(curr);
    }
    return true;
}