# 2023q1 Homework1 (lab0)
contributed by < `dYu0y` >
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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): 20
On-line CPU(s) list: 0-19
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 14
Socket(s): 1
Stepping: 3
CPU max MHz: 4700.0000
CPU min MHz: 400.0000
BogoMIPS: 5376.00
```
## 開發過程
### 對結構串接方式誤會
一開始誤會了結構串接的方式，畢竟從作業的描述與老師在上課時的操作可以看出，這裡的佇列實際上有著雙層的結構。
:::warning
不要濫用詞彙，請回去翻閱你的數學課本，理解「二維」的定義。
:notes: jserv
:::
使用者可以透過命令 `new` 來建立一個一維的佇列，這個佇列內可以存放多個字串。如果使用者多次呼叫 new 命令，外層會有另外一個佇列，將這些使用者建立的所有一維佇列串接起來，並且可以透過 `prev` 和 `next` 命令在這些佇列間切換。
於是在一開始看到 `queue_contex_t` 的定義時：
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
誤以為 `q` 是用來指向用來存放字串的佇列 `list_head` 的指標，而 `chain` 則是用來串接所有透過使用者呼叫 `new` 命令建立的佇列。
所以 `q_new` 寫成了下面這樣：
```c
// in queue.c
struct list_head *q_new()
{
queue_contex_t *queue = (queue_contex_t *) malloc(sizeof(queue_contex_t));
if (!queue) {
return NULL;
}
queue->q = (struct list_head *) malloc(sizeof(struct list_head));
if (!queue->q) {
free(queue);
return NULL;
}
INIT_LIST_HEAD(&queue->chain);
INIT_LIST_HEAD(queue->q);
return &queue->chain;
}
```
後續在完成諸如對 `q_insert` 與 `q_free` 等函式的實作並開始進行測試時，發現總是有記憶體沒有被釋放，即便我看不出來我的 `q_free` 哪裡有寫錯。
當時 `q_free` 的實作：
```c
// in queue.c
void q_free(struct list_head *l)
{
queue_contex_t *queue = container_of(l, queue_contex_t, chain);
element_t *iter, *safe;
list_for_each_entry_safe (iter, safe, queue->q, list) {
q_release_element(iter);
}
free(queue->q);
free(queue);
}
```
執行的結果：
```shell
$ ./qtest
cmd> new
l = []
cmd> ih RAND 3
l = [sfxup fhjvevv dmeht]
cmd> free
l = NULL
ERROR: There is no queue, but 6 blocks are still allocated
```
經過幾輪測試，發現沒釋放的記憶體區塊數量正好是插入節點數量的兩倍，因此推測應該是 `insert` 過程中新增的節點與複製的字串這兩塊記憶體沒有被釋放，才會產生這個現象。
`insert` 的部分程式碼節錄：
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new = (element_t *) malloc(sizeof(element_t));
if (!new) {
return false;
}
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
}
// ...後續部分
}
```
於是我感到很疑惑，因為這就代表了我的 `q_free` 實作中，`list_foreach_entry_safe` 的迴圈部分並沒有被執行，也就是說下方程式碼的第 6 ~ 8 行的迴圈，因為不明的原因，沒有正確的將佇列的每個節點進行正確的釋放。
```c=
// in queue.c
void q_free(struct list_head *l)
{
queue_contex_t *queue = container_of(l, queue_contex_t, chain);
element_t *iter, *safe;
list_for_each_entry_safe (iter, safe, queue->q, list) {
q_release_element(iter);
}
free(queue->q);
free(queue);
}
```
為了了解到底發生了什麼事，我決定使用 gdb 的逐行執行功能來進行除錯。
首先檢查了 Makefile 檔案確定了編譯的參數有加入 `-g`，使得產生的可執行檔是可以被 gdb 讀取的。
之後使用 gdb 除錯的過程如下節錄：
```shell
$ gdb ./qtest
(gdb) b q_free
(gdb) r
cmd> new
l = []
cmd> ih RAND 3
l = [rnjclmi rijzhmx uogrpnpel]
cmd> free
(gdb) layout src
(gdb) n
```
這邊由於很明確出問題的地方就在 `q_free` 之內，於是將斷點設置在其上，奇怪的是當我在 gdb 內使用 n 命令要執行下一行時，卻會直接跳至 `harness.c` 的 `exception_setup` 函式內。
在大略的看過 `harness.c` 的檔案內容後，初步的解決方式是將 `time_limit` 的初始值設定得大一點，避免在使用 gdb 的過程中因為超時而難以除錯。
但是這樣的缺點是每次在 commit 之前還需要將 `time_limit` 的初始值調回來，需要 debug 時又需要將初始值調大。
這邊作個簡單的思考就可以知道，要除錯的過程不太可能這麼麻煩，應該是我漏掉了什麼東西。最後也如我所料，在專案的 `READMD.md` 中，我看到了這一段：
---
## Debugging Facilities
Before using GDB debug `qtest`, there are some routine instructions need to do. The script `scripts/debug.py` covers these instructions and provides basic debug function.
```shell
$ scripts/debug.py -h
usage: debug.py [-h] [-d | -a]
optional arguments:
-h, --help show this help message and exit
-d, --debug Enter gdb shell
-a, --analyze Analyze the core dump file
```
* Enter GDB without interruption by **SIGALRM**.
```
$ scripts/debug.py -d
Reading symbols from lab0-c/qtest...done.
Signal Stop Print Pass to program Description
SIGALRM No No No Alarm clock
Starting program: lab0-c/qtest
cmd>
```
---
原來透過呼叫 `$ scripts/debug.py -d` 進入 gdb 就可以避免觸發 SIGALRM 的中斷。
後來在 gdb 的幫助下找到了 `qtest.c` 中使用者呼叫 `new` 命令時會執行的函式 `do_new`，以下是程式碼節錄：
```c
static bool do_new(int argc, char *argv[])
{
// ...
if (exception_setup(true)) {
queue_contex_t *qctx = malloc(sizeof(queue_contex_t));
list_add_tail(&qctx->chain, &chain.head);
qctx->size = 0;
qctx->q = q_new();
qctx->id = chain.size++;
current = qctx;
}
// ...
}
```
這下才發現原來我對於結構串接方式的認知是有誤的，於是對已經實作的函式進行了修改，終於不會在執行 `./qtest` 時呼叫 `free` 函式之後，看到仍然有尚未釋放的記憶體區塊了。
現階段的程式碼，至少能先通過 `$ make check`
> commit [e89243d](https://github.com/dYu0y/lab0-c/commit/e89243d)
目前這個 commit 裡面含有的功能太多，之後會使用 patch 的方式拆分為多個只包含單一功能的 commit。
### delete duplicate
我的想法是使用一個迴圈將佇列從頭到尾走訪一遍，檢查是否有含有重複元素的節點，並將那些節點移至另一個待處理佇列中。
等到迴圈結束後，再一次性釋放待處理佇列中所有節點所持有的資源。
這邊比較要注意的是在 `queue.h` 中的註解：
```c
/**
* q_delete_dup() - Delete all nodes that have duplicate string, 148 * leaving only distinct strings from the original queue.
* @head: header of queue
*
* Reference:
* https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
*
* Return: true for success, false if list is NULL.
*/
bool q_delete_dup(struct list_head *head);
```
提到了函式的返回值，只有當傳入的佇列是 NULL 時才回傳 false。
> commit [5d975e1](https://github.com/dyu0y/lab0-c/commit/5d975e1)
---
以下部分還尚未完成
### reverse k
先建立一個計數器 `len` 並將初始值設為 0，透過 linked list api 中的 `list_for_each_safe`
臨時連結：
q_swap:
> commit [7879380](https://github.com/sysprog21/lab0-c/commit/7879380)
q_reverseK:
> commit [3bd2bf6](https://github.com/sysprog21/lab0-c/commit/3bd2bf6)
q_reverse:
> commit [f4770dc3](https://github.com/sysprog21/lab0-c/commit/f4770dc3)
Sign in with Wallet
Connect another wallet