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

### Reviewed by `Chloexyw`
1. 在 `q_insert_head` 和 `q_insert_tail` 中有提到有使用函式 `strncpy`，但實際在 GitHub 中並沒有，若能將 GitHub 和共筆的資訊同步更新可以更方便他人進行討論

### Reviewed by `david965154`
1.
使用經過 `clang-format` 風格修正後的程式碼來解釋實作細節的部份。

2.
在 `q_merge` 你提到了使用 [Strategies for Stable Merge Sorting](https://arxiv.org/pdf/1801.04641.pdf) 來實作，在補上實作細節的同時請介紹其方法及如何實作，若與原本實作方法不同，可以說明使用了什麼方法作替代、造成的差異為何。
?

## 開發環境

:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::

因為原本的WSL2的環境拿來裝自己跑數值模擬實驗的軟體以及套件，過於複雜所以重新買了SSD安裝了新的作業系統：`Ubuntu 22.04.3 LTS`

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 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.

lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 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 5600 6-Core Processor
    CPU family:          25
    Model:               33
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            2
    Frequency boost:     enabled
    CPU max MHz:         4467.2852
    CPU min MHz:         2200.0000
    BogoMIPS:            7000.43

## 教材啟發以及紀錄
### 計算機編碼（數值系統）
在之前修習計算機結構第一門課程就是在講解數值系統以及 `IEEE754` 浮點數，從那時對於計算機領域數學一竅不通的我開始接觸這些組成我們所知的電腦背後所組成的數值系統，在那時候透過 [CS 61C](https://cs61c.org/) 的教材以及講解初步認識了一補數和二補數的概念，這次透過老師所撰寫的文章讓我有對計算機編碼的系統有更多的認識，對於傳統工程背景的我來說群論以及數論這些純數學
是對我來說不曾接觸的事物。
[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E9%98%BF%E8%B2%9D%E7%88%BE%E7%BE%A4%E5%8F%8A%E5%B0%8D%E7%A8%B1%E6%80%A7)

目前簡略了解了在計算機編碼所使用的編碼系統都是群論的延伸及應用，上面這張圖可以透過圓環+溢位的概念和群對稱軸（因為群論最大的目的就是研究對稱性)，可以快速的找到編碼後的數值對應的補數，例如：我們如果要找尋 `0011` 之補數透過群對稱軸可以找到對稱的 `1101` 這個編碼，此編碼正好恰巧為是 `0011` 的二補數，也發現一補數對稱軸以及群對稱軸其實偏差了`0.5`，透過此可以定義我們在數值系統常用的二補數編碼就是透過群對稱軸找到的對稱的編碼也恰巧剛好是透過 `0011` 一補數對稱軸所對稱的數值`1100`加上`0001`的編碼，透過這個概念可以推廣至 8-bits, 16-bits, 32-bits 等系統，關於群論以及數論的基礎概念十分有興趣，<s>待碩士論文撰寫後再來詳細研究才能慢慢了解 linux 核心背後的編碼系統。</s>

:::danger
不要輕易許下承諾，亦避免輕易相信別人的承諾，不然他人隨後就不當你是一回事 —— 前者輕佻，後者好騙。
>謝謝老師指正，學生會注意下次避免再犯 by chihen
:::

### 你所不知道的 C 語言（指標篇）

## 佇列實作
本質上都是應用鏈結串列來去撰寫出佇列內的函式來去完成其功能

### `q_new`
這是我第一個開始撰寫的函式，乍看起來十分簡單實作，但對於不熟悉鏈結串列的我，我分成以下步驟來去下手以及思考
1.重新閱讀[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E7%B0%A1%E5%8C%96%E7%9A%84%E5%AF%A6%E4%BD%9C) 中的 Linked list 在 Linux 核心原始程式碼-簡化實作的概念。
2.查看 `queue.h` 程式碼註解
3.查看 `list.h` 程式碼註解
4.思考如何產生一個節點

一開始並不知道何從下手，但再次翻閱[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E7%B0%A1%E5%8C%96%E7%9A%84%E5%AF%A6%E4%BD%9C)知道 `linux` 中 `list.h` 是一個雙向環狀鏈結串列其核心的使用概念就是 `list_head` 這個結構體來去每個結構體 下面此圖讓我更好理解其概念。

:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::

且透過 `queue.h` 關於 `q_new` 的描述讓我知道是建立一個空佇列且為雙向環狀鏈結串列，所以思考過程會如下：
先定義結構體 `struct list_head` 後且用 malloc 來去配置記憶體位置給新的 `head` 然後再使用 `INIT_LIST_HEAD` 這個函式初始化 queue 成雙向環狀鏈結串列。

    if (!head)
    return NULL;

為何要做以上操作？ 是因為查看 C 語言規格書 [ISO/IEC 9899](https://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 中的關於 [7.20.3] `malloc`, `realloc`, `calloc` 函式的定義：
> The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object

>If the space cannot be allocated, a null pointer is returned

所以做以上操作是為了檢查是否有成功配置記憶體，若失敗則提早回傳 `NULL` 。

### `q_free`
查看 `queue.h` 逐一走訪鏈結串列並移除節點再釋放記憶體位址，
會使用`list_for_each_entry_safe` 函式等相關函式。

   if (!head)
   return;

:::danger
使用指定的程式碼縮排風格。
:::

在 `queue.h` 程式碼註解提到若是 ` no effect if header is NULL` ，所以必須先檢查 `head` 是否為 `Null` ，然後透過 `list_for_each_entry_safe` 走訪每個節點，再使用 `q_release_element` 這個函式 `release `所有的 `element`，這樣只會剩下開頭定義的 `head` 再使用 `free` 函式釋放記憶體位址

### `q_insert_head`, `q_insert_tail`
查看 `queue.h` 描述到記憶體位址配置沒有成功或是為 `Null` 時為失敗，且 `s` 必須明確指向執行的字串，所以跟之前一樣先必須查詢是否為 `Null pointer`，後面再使用 `list_add` 函式將新節點加入 `list` 中。

    if (!head || !s)
    return false;

:::danger
使用指定的程式碼縮排風格。
:::

透過上述檢查 `head` 和 `s` 是不是 `Null pointer`，然而在 `queue.h` 提及` The function must explicitly allocate space and copy the string into it`，查看 `liunx man page` 可以看到關於 `strcpy、strncpy、memcpy` 等函式相關的描述可得知 `strcpy、strncpy` 函式是從 `src` 複製字串但 `strcpy `必須確認其記憶體位址配置是足夠的且必須用 `Null byte` 結尾 而 `strncpy` 函式類似 `strcpy` 函式但只有複製 `n` 個 `bytes`，故此函式我選用 `strncpy` 函式來完成，而 `queue_insert_tail` `queue_insert_head` 類似只是將 `list_add` 函式更改為 `list_add_tail` 這個函式。

:::danger
改進你的漢語表達，並比對你的說法是否與 C 語言規格書吻合，注意標準函式庫實作的手法。
:::

### `q_remove_head`, `q_remove_tail`

目前評分為 95/100，時間複雜度無法通過。

TODO：
1. 陸續補上實作細節並且說明開發遇到的問題。
2. 運用 Valgrind 排除 qtest 實作的記憶體錯誤
3. 引入 lib/list_sort.c

:::danger
不要濫用 `:::`，以免造成他人編輯筆記的困難。
:::