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

## 開發環境

$ 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:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
    CPU family:          6
    Model:               142
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            12
    CPU max MHz:         4600.0000
    CPU min MHz:         400.0000
    BogoMIPS:            3999.93

:::danger
說好的進度呢？
:::

## 佇列實作與改進
### `q_new`
宣告一個結構指標 head ，並且使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `INIT_LIST_HEAD` 進行初始化 ，讓 next 和 prev 都指向 head本身。 在依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_new() 的註解 ， 當記憶體配置失敗，返回 NULL

:::danger
:warning: 留意詞彙的使用：
* [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
* [詞彙對照表](https://hackmd.io/@l10n-tw/glossaries)

避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","
:::

### `q_free`
直覺的想法是去走訪佇列的每個節點並釋放，使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_for_each_entry_safe` 去走訪每個節點，並釋放記憶體空間， 依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_free() 的註解要去釋放佇列使用的所有儲存空間，所以連同 head 及 element_t 裡成員所指向字串的記憶體區塊也要進行釋放。

:::danger
改進你的漢語表達。
:::

### `q_insert_head`
依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_insert_head() 的註解，把給定的新節點插入在佇列開頭 (LIFO)，並把給定的字串複製並插入在節點裡面。成功返回 true，分配失敗或佇列為 NULL 時返回 false，也就是說有用到 malloc() 這個函式都要進行判斷。

:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement

「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::

一開始實作是先配置要被複製字串長度的記憶體空間，在使用 strcpy() ，進行複製。在使用 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_add()`將節點加入在串列的開頭。但根據老師 lab0 教材裡的 (依據 CERN [Common vulnerabilities guide for C programmers](https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml) 建議而移除 gets / sprintf / strcpy 等不安全的函式)，改用 strncpy() 進行複製。
> The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

在 `make test` 的時候第十一項測試沒有通過，錯誤訊息如下:

+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
ERROR: Freed queue, but 4 blocks are still allocated
---     trace-11-malloc 0/6

經過除錯之後是在判斷配置字串是否成功時，若失敗時需要連同節點一起釋放掉，而不是直接返回 false。

### `q_insert_tail`
與 `q_insert_head` 實做的想法類似，把給定的新節點插入在佇列結尾 (FIFO)，只須把 [list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_add()` 改成 `list_add_tail()`。

### `q_remove_head`
依 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 裡 q_remove_head() 的註解，把佇列開頭的節點移除，其中 "移除" 與 "刪除" 不同，element 與字串所使用的空間不應被釋放。

想法是利用[list.h ](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_entry` 找出第一個節點的位址，若 sp 不為 NULL ， 複製字串到 sp ，再使用 `list_del_init` 移除並且初始化。這邊不能使用 `list_del ` 的原因是未初始化，若存取該節點的`next` 或 `prev` 指標是不安全的。一開始對 `LIST_POISONING` 的用途不是很了解，但參考 [2024-02-{20,27} 問答簡記](https://hackmd.io/YCnIwo_0R-GaYjISEZwG1A?view#%E7%82%BA%E4%BD%95-listh-%E9%81%B8%E5%AE%9A-0x00100100-%E8%88%87-0x00200200-%E4%BD%9C%E7%82%BA%E7%84%A1%E6%95%88%E7%9A%84%E5%9C%B0%E5%9D%80%EF%BC%9F) 解開心中的疑惑。

### `q_remove_tail`
與 `q_remove_tail` 實做想法相當類似，只須把 list_entry 中的第一個參數 `head->next` (佇列第一個節點) 改成 `head->prev` (佇列最後一個節點)。

### `q_size`
使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 中的 `list_for_each` 去走訪每個節點，並計算節點個數。

### `q_delete_mid`
考慮到環狀佇列，使用 `fnt` 及 `end` 兩個指標，前者從佇列的開頭往後走訪，後者從佇列的尾端往前走訪。有兩種情況，第一種為佇列上的節點是奇數個，當 `fnt == end`，則此節點為中間點;第二種為佇列上的節點是偶數個，當`fnt` 與 `end` 鄰近，也就是`fnt->next == end` ，則 `end` 為中間點。

:::danger
改進你的漢語表達。
:::

### `q_delete_dup`

### `q_swap`

### `q_reverse`
使用 `list_for_each_safe()` 去走訪每個節點，並把當前 `*curr` 所指到的節點透過 `list_move()` 移動到 head 的開頭

### `q_reverse_k`

### `q_sort`

### `q_ascend`

### `q_descend`

### `q_merge`