# 2024q1 Homework1 (lab0)
contributed by < `ihost1002` >
## 開發環境
```shell
$ 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: 39 bits physical, 48
bits virtual
Byte Order: Little Endian
CPU(s): 6
On-line CPU(s) list: 0-5
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) ni5-8400 CPU @ 2.80GHz
CPU family: 6
Model: 158
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 5599.85
```
## 背景知識
### C 語言規格書
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
C99 ( `ISO/IEC 9899:1999` ): [N1256](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 、 [1999](https://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf)
Note : 上面第一個參考來自[你所不知道的C語言：開發工具和規格標準](https://hackmd.io/@sysprog/c-standards)，第二個參考是自google搜尋到的，在[課程討論區](https://app.gitter.im/#/room/#embedded2015_guts-general:gitter.im)感謝 `Niclas3` 同學的回覆，個人理解後應該是 `N1256` 版本較新，所以後來查找資料都**以 `N1256` 為主**
`Niclas` 同學的回覆如下（時間為2024/2/19):
<s>
</s>
文字內容:
Niclas3 (Niclas) : TC 应该是技术勘误的意思，
https://www.open-std.org/jtc1/sc22/wg14/www/standards.html#9899 这里是我找到的相关网页
Niclas3 (Niclas) : n1507 应该是 C11 的文档版本号。C99 经过3次修订所以最终草稿应该是 TC3 。我一开始提供的文档是一个草稿文档， ihost1002 给的应该是 iSO 的正式版文档，我查到的资料看来两者没有内容上的区别。如有遗漏还望指正
:::danger
文字訊息請避免用圖片來表示，否則不好搜尋和分類。
:::
## 針對佇列操作的程式碼實作
### `q_size`
```c
/**
* q_size() - Get the size of the queue
* @head: header of queue
*
* Return: the number of elements in queue, zero if queue is NULL or empty
*/
int q_size(struct list_head *head);
```
取得 佇列 `head` 鏈結到的所有節點的數量，如果佇列是 `NULL` 或 `empty` 則回傳 `NULL`。 `empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
1. 實作 `queue.c` 裡的 `q_size`
2. git commit -a
3. clang-format -i queue.c
4. 跳至 1 直到 make check 能正常回傳 node 數量
5. 修改 queue.h
6. git commit -a 顯示不能修改.h
7. git restore queue.h
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
:::
詳細內容：`make check`結果與`lab0`頁面一開始的結果不同，`lab0`頁面如下：
參閱 [lab0-c](https://github.com/sysprog21/lab0-c) 的文件 (即 `README.md` 檔案) 後，我們得知能用以下命令測試 `qtest`:
```shell
$ make check
```
對應的程式輸出如下:
```
./qtest -v 3 -f traces/trace-eg.cmd
cmd>
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
q = NULL
cmd> # Create empty queue
cmd> new
q = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
```
:::danger
避免贅詞。
:::
而我自己的結果如下：
```shell
$ make check
```
對應的程式輸出如下:
```
./qtest -v 3 -f traces/trace-eg.cmd
# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
l = NULL
# Create empty queue
l = NULL
# See how long it is
Warning: Calling size on null queue
ERROR: Computed queue size as -1, but correct value is 0
l = NULL
# Fill it with some values. First at the head
Warning: Calling insert head on null queue
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
```
:::danger
不要濫用 \:\:\:info 一類的標注，內容才是關鍵！
:::
因此想要找出問題點，由上可知以下差異
1. 在新增queue的時候沒有成功，仍顯示 `NULL`
2. 在輸入size的時候出現錯誤
3. queue的名稱為 `l` ，而 `lab0` 顯示的queue名稱為 `q`
:::danger
command 的翻譯是「命令」，而非「指令」
:::
因為沒有認真看題目敘述，所以試著自己尋找這個錯誤是從哪裡出現的，而 `qtest` 是由許多個 .o 執行檔組合而成，因此先在` linux cmd` 執行命令
`$ ./qtest`
進到 `cmd >` ,試著打 `help` 找到命令 `size` ,顯示為回傳 `queue` 的 `size` ,然後又看了 `new` 是新增一個 `queue` ,因此猜測出錯的 `source` 檔案可能為跟處理 `queue` 有關，下了命令
`$ ls *.c`
:::danger
command 的翻譯是「命令」，而非「指令」
:::
找到最有可能的檔案為 `queue.c` ,用 `vim` 打開，找到
```c
/* Return number of elements in queue */
int q_size(struct list_head *head) {
return -1;
}
```
這時我實際上是先跳去寫 `q_new` ，當 `q_new` 完成後才來寫 `q_size` ，接著我先去找 `struct list_head` 這個 `struct` 宣告才知道要如何處理節點數量，然後一番查找下在 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 的第 18 到 38 行找到它的宣告如下：
```c
/**
* struct list_head - Head and node of a doubly-linked list
* @prev: pointer to the previous node in the list
* @next: pointer to the next node in the list
*
* The simple doubly-linked list consists of a head and nodes attached to
* this head. Both node and head share the same struct type. The list_*
* functions and macros can be used to access and modify this data structure.
*
* The @prev pointer of the list head points to the last list node of the
* list and @next points to the first list node of the list. For an empty list,
* both member variables point to the head.
*
* The list nodes are usually embedded in a container structure which holds the
* actual data. Such container structure is called entry. The helper list_entry
* can be used to calculate the structure address from the address of the node.
*/
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
所以 `struct list_head` 是一個有兩個 member `prev` 和 `next` 的 `struct` , 而 `struct list_head *` 則是指向這個 `struct` 的 `pointer` ，兩個 member 都是指向 `struct list_head *` 的 `pointer` 。
目前完成結果如下：
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int size = 0;
const struct list_head *count = head;
while (count->next != head) {
count = count->next;
size++;
}
return size;
}
```
:::info
避免贅詞。
:::
以下是我的作法：
1. 假如 `head` 為 `NULL` 或是 `head` 存在但 `prev` 與 `next` 皆指向 `head` 則回傳 ⍬ ，這邊借用到 `list.h` 裡的 `list_empty` 來幫忙判別後者的結果。
2. 宣告一個 `int` `type` 的 `size` 來累計 `node` 數;宣告 `const struct list_head *count` 接收 `head` 的 `value` ，然後下 `while` 迴圈判斷當 `count` 的 `next` 指向 `head` 的時候結束迴圈，迴圈裡每次 `count` 更新為 `next` 指向的 `value` ，`size` 每次 +1 。
當我以為寫到這裡結束的時候看到 `if statement` 後面沒加 `curly braces` 但是竟然通過 `pre-commit hook` 檢查，所以馬上更正。
```diff
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
+ if (!head || list_empty(head)) {
return 0;
+ }
int size = 0;
const struct list_head *count = head;
while (count->next != head) {
count = count->next;
size++;
}
return size;
}
```
這邊 markdown 語法是參考 [kdnvt](https://hackmd.io/@sysprog/linux2022-sample-lab0)
:::danger
為何不閱讀第一手材料呢？
:::
### `q_new`
```c
/**
* q_new() - Create an empty queue whose next and prev pointer point to itself
*
* Return: NULL for allocation failed
*/
struct list_head *q_new();
```
建立一個空的佇列，其成員 `@next`、`@prev` 皆`指向它自己`。如果成功就回傳這個佇列，由於區域變數有效範圍只在當前這個 code block `{}` 裡，所以應使用 dynamic memory allocation, `mlloac()` 。而 C99 規格書 [n1256](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 第 313 頁說道:
>7.20.3 Memory management functions
1 The order and contiguity of storage allocated by successive calls to the calloc,
malloc, and realloc functions is unspecified. The pointer returned if the allocation
succeeds is suitably aligned so that it may be assigned to a pointer to any type of object
and then used to access such an object or an array of such objects in the space allocated(until the space is explicitly deallocated). The lifetime of an allocated object extends from the allocation until the deallocation.
...
所以理論上由`記憶體管理函式`成功分配的空間，直到 `deallocated` 之前都是有效的。
回到上一句，如果 `malloc()` 失敗回傳 `NULL`。
而依照 C99 規格書 [n1256](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 第 314 頁說道:
>7.20.3.3 The malloc function
Synopsis
1 #include <stdlib.h>
void *malloc(size_t size);
Description
2 The malloc function allocates space for an object whose size is specified by size and
whose value is indeterminate.
Returns
3 The malloc function returns either a null pointer or a pointer to the allocated space.
所以 `malloc()` 失敗的時候也是回傳 `NULL`。
程式碼如下:
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head) {
return NULL;
}
INIT_LIST_HEAD(head);
return head;
}
```
但有想到一個問題，放在`疑問`標題那邊
### q_insert_head
```c
/**
* q_insert_head() - Insert an element in the head
* @head: header of queue
* @s: string would be inserted
*
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*
* Return: true for success, false for allocation failed or queue is NULL
*/
bool q_insert_head(struct list_head *head, char *s);
```
在佇列 `head` 的開頭插入一個 `element`。這邊 `element` 指的是 `element_t` 成員 `list` 。`@s` 是將被複製的字串，複製到 `element_t` 成員 `value` 所指向的記憶體位址，這個位址所指向的空間必須 `allocated` 且大小剛剛好是字串長度加上 `\⍬`。成功回傳 `true`， 如果 `allocation` 失敗或佇列是 `NULL` 則回傳 `false`。
在開頭想先寫到，在瀏覽 [lab0-c](https://github.com/sysprog21/lab0-c) 時在 commit [04cf2c6](https://github.com/sysprog21/lab0-c/commit/04cf2c67e1e62901874907b7483659132da4c814) 看到註解寫到 `strcpy` 是不安全的函式，而後來再搜尋一次關鍵字 `strcpy` 時找到 [lab0-c/scripts
/pre-commit.hook](https://github.com/sysprog21/lab0-c/blob/39c85e97b1b5b7b222a23e9d2066419463ab750b/scripts/pre-commit.hook#L111) ，所以 `commit` 的時候 `pre-commit hook` 會檢查如果使用這幾個 function 就不會過，提醒自己記得不要使用 `gets`、`sprintf`、`strcpy`，所以在複製字串到 `element_t` 裡的 `value`member 的功能可改用 `strncpy` 。接著我一直在想 `struct list_head *` 類型跟 `element_t *` 不同啊！不能把前者指向後者啊，可是 [lab0-c/queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 第58行清楚說道要 `Insert an element in the head` ，這邊卡了應該有半天，後來真的想不出辦法，就去看 2023 年其他同學的寫法，感謝 [25077667](https://hackmd.io/@25077667/lab0-2023) 同學提交的作業資料，當看到這一行的的時候:
```c
op(&me->list, head);
```
終於了解原來 `insert` 是指 `element_t` 的成員 `list` 而且要轉成`struct list_head *` ，而且同學使用 `helper function` 及 `pointer to a function` 來**避免重複的程式碼**真是太棒了! 但後來想想畢竟不是我自己想到的，所以我還是先自己寫看看。一開始程式碼如下:
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
/* Return false if head is NULL */
if (!head) {
return false;
}
/* Create new element_t with malloc and with explicitly enough space of element_t->value */
int len = strlen(s) + 1;
element_t *e = malloc(sizeof(char) * len + sizeof(struct list_head));
/* Return false if e is NULL */
if (!e) {
return false;
}
/* Copy Strings into element_t->value */
strncpy(e->value, s, len);
/* Add elemet_t->list to head */
list_add(&e->list, head);
return true;
}
```
結果如下：
`make check`
```
./qtest -v 3 -f traces/trace-eg.cmd
# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
l = NULL
# Create empty queue
l = []
# See how long it is
Queue size = 0
l = []
# Fill it with some values. First at the head
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
```
很顯然在填入`字串`的時候有問題，最後結論就是因為對 `malloc` 以及使用的是 `type` 還是 `type *` 搞不清楚，這是事後來寫結果，但是我一開始以為「malloc 可以在使用的時候分別宣告給 `char` 以及 `struct list_head` 的空間」，結果是不行 ; 然後換成 `element_t *` variable的時候，我一直糾結在「如果 `malloc` 已經分配一個 `element_t` 空間給 `element_t *` ，那不就代表成員 `value` 給定的空間只有一個 `char`? 那我要存`字串`進去的時候我還要再 `malloc` 一次足夠的空間給 `value` ，這樣我不就要先釋放 `value` 原來的位置然後再 `malloc` 一次？」結果***我的觀念是錯的***，結論是 `malloc` 給 `element_t *` 的時候，分配給 `value` 的型別是 `char *` 這樣大小的空間，所以實際分配的是 `char **`: 它儲存 `char *value` variable的位址，不是 `char` ，所以我在使用 `value` 的時候本來就要再 `malloc` 一次剛好大小的 `char` 給 `value` ，並且在使用 `free` 釋放`variable` 空間的時候要先釋放 `element_t->value` 再釋放 `element_t` 。程式碼如下:
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
/* Return false if head is NULL */
if (!head) {
return false;
}
/* Create new element_t with malloc */
element_t *e = malloc(sizeof(element_t));
/* Return false if e is NULL */
if (!e) {
return false;
}
/* Create explicitly enough space of new elemet_t->value */
int len = strlen(s) + 1;
e->value = malloc(sizeof(char) * len);
/* Return false if e->value is NULL*/
if (!(e->value)) {
free(e);
return false;
}
/* Copy Strings into element_t->value */
strncpy(e->value, s, len);
/* Add elemet_t->list to head */
list_add(&e->list, head);
return true;
}
```
### q_insert_tail
```c
/**
* q_insert_tail() - Insert an element at the tail
* @head: header of queue
* @s: string would be inserted
*
* Argument s points to the string to be stored.
* The function must explicitly allocate space and copy the string into it.
*
* Return: true for success, false for allocation failed or queue is NULL
*/
bool q_insert_tail(struct list_head *head, char *s);
```
在佇列 `head` 的結尾插入一個 `element`。這邊的 `element` 指的是 `element_t` 成員 `list`。`@s` 是將被複製的字串，複製到 `element_t` 成員 `value` 所指向的記憶體位址，這個位址所指向的空間必須 `allocated` 且大小剛剛好是字串長度加上 `\⍬`。成功回傳 `true`， 如果 `allocation` 失敗或佇列是 `NULL` 則回傳 `false`。
同 `q_insert_head` 比照辦理，程式碼如下:
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
/* Return false if head is NULL */
if (!head) {
return false;
}
/* Create new element_t with malloc */
element_t *e = malloc(sizeof(element_t));
/* Return false if e is NULL */
if (!e) {
return false;
}
/* Create explicitly enough space of new elemet_t->value */
int len = strlen(s) + 1;
e->value = malloc(sizeof(char) * len);
/* Return false if e->value is NULL*/
if (!(e->value)) {
free(e);
return false;
}
/* Copy Strings into element_t->value */
strncpy(e->value, s, len);
/* Add elemet_t->list to head */
list_add_tail(&e->list, head);
return true;
}
```
寫到這邊，我本來以為應該結束了，但又想到了，這個 `element_t` 成員 `list` 尚未初始化，就像 [list.h](https://github.com/sysprog21/lab0-c/blob/39c85e97b1b5b7b222a23e9d2066419463ab750b/list.h) 第 73-80 行寫到的:
> \* A node is usually linked inside a list, will be added to a list in
> \* the near future or the entry containing the node will be free'd soon.
> \*
> \* But an unlinked node may be given to a function which uses list_del(_init)
> \* before it ends up in a previously mentioned state. The list_del(_init) on an
> \* initialized node is well defined and safe. But the result of a
> \* list_del(_init) on an uninitialized node is undefined (unrelated memory is
> \* modified, crashes, ...).
所以我應該先 `initialize list` 再做後續動作。
### q_free
```c
/**
* q_free() - Free all storage used by queue, no effect if header is NULL
* @head: header of queue
*/
void q_free(struct list_head *head);
```
釋放所有被佇列 `head` 使用到的空間，如果佇列本身是 `NULL` 不造成任何影響。
初始程式碼:
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (!head) {
return;
}
if (list_empty(head)) {
free(head);
return;
}
struct list_head *q = head->next;
while (q->next != head) {
struct list_head *r = q->next;
free(q);
q = r;
}
free(q);
free(head);
}
```
執行結果:
```shell
$ make check
./qtest -v 3 -f traces/trace-eg.cmd
# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
l = NULL
# Create empty queue
l = []
# See how long it is
Queue size = 0
l = []
# Fill it with some values. First at the head
l = [dolphin]
l = [bear dolphin]
l = [gerbil bear dolphin]
# Now at the tail
l = [gerbil bear dolphin meerkat]
l = [gerbil bear dolphin meerkat bear]
# Reverse it
l = [gerbil bear dolphin meerkat bear]
# See how long it is
Queue size = 5
l = [gerbil bear dolphin meerkat bear]
# Delete queue. Goes back to a NULL queue.
ERROR: Attempted to free unallocated block. Address = 0x560ec14ce1c8
ERROR: Attempted to free unallocated or corrupted block. Address = 0x560ec14ce1c8
Segmentation fault occurred. You dereferenced a NULL or invalid pointermake: *** [Makefile:57: check] Aborted (core dumped)
```
由上可知:
在 `Delete queue` 時發生錯誤，錯誤原因有2:
1. 應該 `free()` 的是 `element_t->value` 及 `element_t`，非 `element_t->list`
2. `free()` 之前應該先把當前 `element_t->list` 的 `@prev` 和 `@next` 值指向 `NULL` 或是 `head`，我的作法是後者，使用 [INIT_LIST_HEAD()](https://github.com/sysprog21/lab0-c/blob/39c85e97b1b5b7b222a23e9d2066419463ab750b/list.h)，第 67 到 86 行。
完成的程式碼:
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
if (!head) {
return;
}
if (list_empty(head)) {
free(head);
return;
}
struct list_head *q = head->next;
element_t *t = NULL;
while (q->next != head) {
struct list_head *r = q->next;
INIT_LIST_HEAD(q);
t = container_of(q, element_t, list);
free(t->value);
free(t);
q = r;
}
INIT_LIST_HEAD(q);
t = container_of(q, element_t, list);
free(t->value);
free(t);
free(head);
}
```
```shell
$ make check
CC queue.o
LD qtest
./qtest -v 3 -f traces/trace-eg.cmd
# Demonstration of queue testing framework
# Use help command to see list of commands and options
# Initial queue is NULL.
l = NULL
# Create empty queue
l = []
# See how long it is
Queue size = 0
l = []
# Fill it with some values. First at the head
l = [dolphin]
l = [bear dolphin]
l = [gerbil bear dolphin]
# Now at the tail
l = [gerbil bear dolphin meerkat]
l = [gerbil bear dolphin meerkat bear]
# Reverse it
l = [gerbil bear dolphin meerkat bear]
# See how long it is
Queue size = 5
l = [gerbil bear dolphin meerkat bear]
# Delete queue. Goes back to a NULL queue.
l = NULL
# Exit program
Freeing queue
```
### q_remove_head
```c
/**
* q_remove_head() - Remove the element from head of queue
* @head: header of queue
* @sp: string would be inserted
* @bufsize: size of the string
*
* If sp is non-NULL and an element is removed, copy the removed string to *sp
* (up to a maximum of bufsize-1 characters, plus a null terminator.)
*
* NOTE: "remove" is different from "delete"
* The space used by the list element and the string should not be freed.
* The only thing "remove" need to do is unlink it.
*
* Reference:
* https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
*
* Return: the pointer to element, %NULL if queue is NULL or empty.
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize);
```
在佇列 `head` 的開頭 **remove** 一個 `element`， 即 `element_t *`。註記裡寫到 **remove** 是斷開鏈結但 `element_t *` 及 `element_t->value` 指向的空間不被釋放，而 **delete** 就是前兩者指向的空間都要被釋放。成功則回傳 `element_t *`，如果佇列 `head` 是 `NULL` 或是`empty` 則回傳 `NULL`。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。如果 `@sp` 不是 `NULL` 且 `element` 即 **element_t \*** 已被 **remove**， 則從 `element_t->value` 複製 `bufsize-1` 個`字元` 及結尾 `\⍬` 到 `@sp`。所以可理解為只要複製不需要再 `alloacate`。
這邊寫出來了，還在整理。
### q_remove_tail
```c
/**
* q_remove_tail() - Remove the element from tail of queue
* @head: header of queue
* @sp: string would be inserted
* @bufsize: size of the string
*
* Return: the pointer to element, %NULL if queue is NULL or empty.
*/
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize);
```
在佇列 `head` 的結尾 **remove** 一個 `element`， 即 `element_t *`。**remove** 及 **delete** 的差異參考 `q_remove_head()`。成功則回傳 `element_t *`，如果佇列 `head` 是 `NULL` 或是`empty` 則回傳 `NULL`。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。如果 `@sp` 不是 `NULL` 且 `element` 即 **element_t** 已被 **remove**， 則從 `element_t->value` 複製 `bufsize-1` 個`字元` 及結尾 `\⍬` 到 `@sp`。所以可理解為只要**複製**不需要再 `alloacate`。
同 q_remove_head
### q_delete_mid
```c
/**
* q_delete_mid() - Delete the middle node in queue
* @head: header of queue
*
* The middle node of a linked list of size n is the
* ⌊n / 2⌋th node from the start using 0-based indexing.
* If there're six elements, the third member should be returned.
*
* Reference:
* https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
*
* Return: true for success, false if list is NULL or empty.
*/
bool q_delete_mid(struct list_head *head);
```
`delete` 佇列 `head` 的`中間節點`，假設`節點總數`為 `n`， 索引以 `⍬` 為第一個節點，則取 `n / 2` 當做`中間節點`，這邊舉例`節點總數`為 `6`，則取 `n / 2 = 3` 為中間節點，對應索引為 `3 - 1 = 2`，若`總節點數`為`奇數`，則如 C 語言整數運算取`商數`為中間數，如`總節點數`為 `7`，則`中間節點`為第`3`個，索引為`2`。這邊 `delete` 表示要釋放 `element_t *` 和 `element_t->value`。
### q_delete_dup
```c
/**
* q_delete_dup() - Delete all nodes that have duplicate string,
* 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);
```
`delete` 所有相同`字串`內容的節點，留下`唯一不重複的字串`的節點。成功則回傳 `true`，如果佇列 `head` 為 `NULL` 則回傳 `false`。所以如果各節點儲存的`字串`都是`不同的`，也回傳`true`。這邊想到一個問題，假設索引 `0` - `2` 節點 儲存的`字串`依序為 `"abc"、 "def"、 "abc"`，則經過 `delete` 之後節點索引 `0` - `1` 儲存的`字串`依序為 `"abc"、 "def"` 還是 `"def"、 "abc"`，這邊沒有明確說明，要進一步參考 `leetcode` 題目。
看完題目之後，前述完全不對，是只要重複的都刪除，所以前例結果為 `"def"`。
### q_swap
```c
/**
* q_swap() - Swap every two adjacent nodes
* @head: header of queue
*
* Reference:
* https://leetcode.com/problems/swap-nodes-in-pairs/
*/
void q_swap(struct list_head *head);
```
初始理解為交換與佇列 `head` 相鄰的節點，即交換 `head->prev` 與 `head->next`。看過 `leetcode` 題目以及自己測試後與初始理解不同，它是兩兩相鄰的一對節點作交換，所以`奇數`個節點的最後一個不做改變。例子: `"1", "3", "5", "7", "9"` 經 `q_swap()` 結果為 `"3", "1", "7", "5", "9"`。由於 `list_head` 是一個 `circular doubly linked list`，如果前例傳進來的是 `head->next->next`，則原來例子變成 `"5", "7", "9", "1", "3"`，其結果為 `"7", "5", "1", "9", "3"`。目前想到此函式與其它函式有相關的部份應該跟排序有關。
### q_reverse
```c
/**
* q_reverse() - Reverse elements in queue
* @head: header of queue
*
* No effect if queue is NULL or empty.
* This function should not allocate or free any list elements
* (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
* It should rearrange the existing ones.
*/
void q_reverse(struct list_head *head);
```
反轉佇列 `head` 的`節點順序`，假如原來有三個節點，索引 `0 - 2` `字串`依序為 `"How"、 "are"、 "you?"`，經過反轉後從索引 `0 - 2` `字串`依序為 `"you?"、 "are"、 "How"`。如果佇列 `head`為 `NULL` 或 `empty` 則不造成任何影響。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。這個函式不該額外 `allocate` 或 `free` 任何 `element_t`，即不使用 `q_insert_*`、 `q_remove_*`、 `q_delete_*` 等相關功能的函式。只有重新排列`既存節點`的順序。
### q_reverseK
```c
/**
* q_reverseK() - Given the head of a linked list, reverse the nodes of the list
* k at a time.
* @head: header of queue
* @k: is a positive integer and is less than or equal to the length of the
* linked list.
*
* No effect if queue is NULL or empty. If there has only one element, do
* nothing.
*
* Reference:
* https://leetcode.com/problems/reverse-nodes-in-k-group/
*/
void q_reverseK(struct list_head *head, int k);
```
以 `k` 為一組反轉佇列 `head` 前 `k` 個節點順序，原來索引 `0, 1, 2, ... k-2, k-1` 變為 `k-1, k-2, ... 2, 1, 0`，後接 `k, k+1, ... n-1`, 其中 `n` 為總節點數， `k 為正整數且 k <= n`。後續 `k, k+1, ... n-2，n-1` 如果節點數量大於或等於 `k`，則重複之前的反轉作業，如果節點數量小於 `k`，則剩餘這些節點保持不變。佇列是 `NULL` 或 `empty` 則不造成任何影響。如果佇列剛好只有一個節點，則不做任何改變。 `empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。舉例:佇列 `head` 有 `5` 個 節點，其中從索引 `0, 1, ..., 4` 分別為 `"aa", "bb", "cc", "dd", "ee"`， 則 `q_reverseK(head, 4)` 結果為 `"dd", "cc", "bb", "aa", "ee"`。 `k = 5` 時則功能同 `q_reverse()`， 而 `k > 5` 時不做任何改變。
### q_sort
```c
/**
* q_sort() - Sort elements of queue in ascending/descending order
* @head: header of queue
* @descend: whether or not to sort in descending order
*
* No effect if queue is NULL or empty. If there has only one element, do
* nothing.
*/
void q_sort(struct list_head *head, bool descend);
```
以`遞增`或`遞減`方式排序佇列，個人理解這邊的`遞增`應該是按`字串`由 `a`, `b`, ... , `z` 方式排序，`遞減則相反`， `descend` 值為 `true` 則為`遞減`， `false` 為`遞增`。如果佇列是 `NULL` 或 `empty`則不造成任何影響。如果只有一個節點則不做任何事。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。
:::danger
如何確保目前的測試已涵蓋排序演算法的最差狀況？
:::
> <s>老師，對不起</s> ，之前用留言回覆，現在改在您留言底下回覆，請問您的意思是在完成 q_new、 q_size、q_free、q_insert_head、q_insert_tail 後先考慮測試是否涵蓋排序演算法的最差狀況，例如說要遞增排序但是當前的佇列是遞減排序嗎？
:::warning
不用跟我道歉，你唯一需要道歉的理由是「你不夠強」。參閱 [2024-03-{05,07,12} 問答紀錄](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ)
:::
### q_ascend
```c
/**
* q_ascend() - Remove every node which has a node with a strictly less
* value anywhere to the right side of it.
* @head: header of queue
*
* No effect if queue is NULL or empty. If there has only one element, do
* nothing.
*
* Reference:
* https://leetcode.com/problems/remove-nodes-from-linked-list/
*
* Return: the number of elements in queue after performing operation
*/
int q_ascend(struct list_head *head);
```
在這個佇列 `head` 裡，如果某節點與它之前的所有節點的字串比較是`相對最小`的，則 `remove` 此節點之前的`所有節點`，如果佇列是 `NULL` 或 `empty` 則不造成任何影響。如果佇列只有一個節點則不做任何事。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。回傳經此函式運算後剩下的節點個數。`remove` 與 `delete` 的差別參考 `q_remove_head`。舉例: `"abc", "bc", "A", "cd", "C"` 經 `q_ascend()` 結果為 `"A", "C"`，回傳 `2`。
### q_descend
```c
/**
* q_descend() - Remove every node which has a node with a strictly greater
* value anywhere to the right side of it.
* @head: header of queue
*
* No effect if queue is NULL or empty. If there has only one element, do
* nothing.
*
* Reference:
* https://leetcode.com/problems/remove-nodes-from-linked-list/
*
* Return: the number of elements in queue after performing operation
*/
int q_descend(struct list_head *head);
```
在這個佇列 `head` 裡，如果某節點與它之前的所有節點的字串比較是`相對最大`的，則 `remove` 此節點之前的`所有節點`，如果佇列是 `NULL` 或 `empty` 則不造成任何影響。如果佇列只有一個節點則不做任何事。`empty` 參考 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第 161 - 170 行 `list_empty`，即 佇列 的成員 `@prev` 及 `@next` 皆指向佇列本身。回傳經此函式運算後剩下的節點數。`remove` 與 `delete` 的差別參考 `q_remove_head`。舉例: `"abc", "bc", "z", "cd", "d"` 經 `q_descend()` 結果為 `"z", "d"`，回傳 `2`。
### q_merge
```c
/**
* q_merge() - Merge all the queues into one sorted queue, which is in
* ascending/descending order.
* @head: header of chain
* @descend: whether to merge queues sorted in descending order
*
* This function merge the second to the last queues in the chain into the first
* queue. The queues are guaranteed to be sorted before this function is called.
* No effect if there is only one queue in the chain. Allocation is disallowed
* in this function. There is no need to free the 'queue_contex_t' and its
* member 'q' since they will be released externally. However, q_merge() is
* responsible for making the queues to be NULL-queue, except the first one.
*
* Reference:
* https://leetcode.com/problems/merge-k-sorted-lists/
*
* Return: the number of elements in queue after merging
*/
int q_merge(struct list_head *head, bool descend);
```
從 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 第 28 - 40 行，在 `queue_contex_t` 裡的成員 `q` 是某個佇列，由成員 `chain` 來鏈結其他佇列，`id` 為 `⍬` 是這個 `queue_contex_t` 結構的第一個佇列，而這個函式的功能是把 `id` 從`1 - 最後`的其它佇列合併到`第一個` 佇列，並且在呼叫這個函式之前要確保每個佇列都是已經排序好的。如果 `queue_contex_t` 裡只有一個佇列 `q`，則不造成任何影響。這個函式裡不允許 `allocation`，個人理解為不允許配置新的記憶體空間。不須`釋放` `queue_contex_t` 和其成員 `q`，因其會在其他函式裡被 `釋放`。除了第一個佇列外，其它被合併的佇列將變成 `NULL 佇列`。
繼續看 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github)。
## 修正自己的錯誤認知
### list_add
來源: [lab0-c/list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 第88-101行
程式碼:
```c
/**
* list_add() - Add a list node to the beginning of the list
* @node: pointer to the new node
* @head: pointer to the head of the list
*/
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
原來以為是這樣，但是***是錯的***：
1.
> head 和 node
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="" label="" style="invis" height="0.65" width="1"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
{rank = same; new_node n0; }
{rank = same; n1 invis1 }
/* 'insivible' edge to adjust node placement */
edge [color="red" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 [weight="2"];
n1:s -> invis1:n;
}
```
2.
> struct list_head \*next = head->next;
> 錯在這邊， `next` 應指向 `head`，不是指向另一個 `node`
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
n0:p2:c -> n0:e [color="red"];
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* struct list_head *next = head->next; */
n0:p2:c -> n2:w [color="orange"];
{rank = same; new_node n0; }
{rank = same; n1 invis1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 -> n2 [weight="3"];
n1:s -> invis1:n;
invis1 -> next;
}
```
3.
>next->prev = node;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* struct list_head *next = head->next; */
n0:p2:c -> n2:w;
/* next->prev = node */
n2:p1:c -> n1:se [color="orange" weight="0"];
{rank = same; new_node n0; }
{rank = same; n1 invis1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 -> n2 [weight="3"];
n1:s -> invis1:n;
invis1 -> next;
}
```
4.
> node->next = next;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e [color="red"];
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* struct list_head *next = head->next; */
n0:p2:c -> n2:w;
/* next->prev = node */
n2:p1:c -> n1:se [weight="0"];
/* node->next = next; */
n1:p2:c -> n2:nw [weight="0" color="orange"]
{rank = same; new_node n0; }
{rank = same; n1 invis1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 -> n2 [weight="3"];
n1:s -> invis1:n;
invis1 -> next;
}
```
5.
> node->prev = head;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="3"];
n1:p1:c -> n1:w [color="red"];
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* struct list_head *next = head->next; */
n0:p2:c -> n2:w;
/* next->prev = node */
n2:p1:c -> n1:se [weight="0"];
/* node->next = next; */
n1:p2:c -> n2:nw [weight="0"]
/* node->prev = head; */
n1:p1:c -> n0:e [weight="" color="orange"];
{rank = same; new_node n0; }
{rank = same; n1 invis1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 -> n2 [weight="3"];
n1:s -> invis1:n;
invis1 -> next;
}
```
6.
> head->next = node;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="3"];
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* struct list_head *next = head->next; */
n0:p2:c -> n2:w [color="red"];
/* next->prev = node */
n2:p1:c -> n1:se [weight="0"];
/* node->next = next; */
n1:p2:c -> n2:nw [weight="0"];
/* node->prev = head; */
n1:p1:c -> n0:e [weight="0"];
/* head->next = node; */
n0:p2:c -> n1:w [color="orange"];
{rank = same; new_node n0; }
{rank = same; n1 invis1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 -> n2 [weight="3"];
n1:s -> invis1:n;
invis1 -> next;
}
```
7.
> 變成
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
//invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
/* head->next = node; */
n0:p2:c -> n1:w [style="invis"];
n0:p2:c -> n1:w;
/* draw node and struct list_head where node point to */
new_node:e -> n1:sw;
/* node->next = next; */
n1:p2:c -> n2:w [style="invis"];
n1:p2:c -> n2:w;
/* draw next and sturct list_head where next point to */
next:e -> n2:sw
/* next->prev = node */
n2:p1:c -> n1:e;
n2:p1:c -> n1:e [style="invis"];
/* node->prev = head; */
n1:p1:c -> n0:e;
n1:p1:c -> n0:e [style="invis"];
{rank = same; n0 new_node; }
{rank = same; n1 next; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
n0 -> n1 -> n2;
}
```
***正確的***：
1.
> head 和 node
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="" label="" style="invis" height="0.65" width="1"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w;
n0:p1:c -> n0:w;
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
{rank = same; new_node n0; }
{rank = same; n1 invis1 }
/* 'insivible' edge to adjust node placement */
edge [color="red" style="invis"];
new_node:s -> n0:n;
n0 -> invis1 [weight="2"];
n1:s -> invis1:n;
}
```
2.
> struct list_head \*next = head->next;
> `next` 指向 `head`
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w[weight="2"];
n0:p1:c -> n0:w;
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
/* struct list_head *next = head->next; */
next:e -> n0:sw [color="orange"];
{rank = same; new_node head; }
{rank = same; invis1 n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> n1 -> invis1 [weight="1"];
invis1 -> n0;
}
```
3.
>next->prev = node;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w[weight="2"];
n0:p1:c -> n0:w[color="red"];
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e;
/* struct list_head *next = head->next; */
next:e -> n0:sw;
/* next->prev = node; */
n1:se -> n0:p1:c [color="orange" arrowtail="vee" arrowhead="dot"];
{rank = same; new_node head; }
{rank = same; invis1 n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> n1 -> invis1 [weight="1"];
invis1 -> n0;
}
```
4.
> node->next = next;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:w[weight="2"];
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="2"];
n1:p1:c -> n1:w;
n1:p2:c -> n1:e [color="red"];
/* struct list_head *next = head->next; */
next:e -> n0:sw;
/* next->prev = node; */
n1:se -> n0:p1:c [arrowtail="vee" arrowhead="dot"];
/* node->next = next; */
n1:p2:c -> n0:nw [color="orange"];
{rank = same; new_node head; }
{rank = same; invis1 n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> n1 -> invis1 [weight="1"];
invis1 -> n0;
}
```
5.
> node->prev = head;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:e -> n0:s[weight="0"];
n0:p2:c -> n0:e;
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="1"];
n1:p1:c -> n1:w [color="red"];
/* struct list_head *next = head->next; */
next:e -> n0:se;
/* next->prev = node; */
n1:se -> n0:p1:c [arrowtail="vee" arrowhead="dot"];
/* node->next = next; */
n1:p2:c -> n0:w;
/* node->prev = head; */
n1:p1:c -> n0:sw [color="orange"];
{rank = same; new_node head; }
{rank = same; invis1 n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> n1 -> invis1 [weight="1"];
invis1 -> n0;
}
```
6.
> head->next = node;
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
n0:s -> head:w [weight="0" arrowtail="vee" arrowhead="dot"];
n0:p2:c -> n0:e [color="red"];
/* draw node and struct list_head where node point to */
new_node:e -> n1:w [weight="1"];
/* struct list_head *next = head->next; */
n0:se -> next:w [arrowtail="vee" arrowhead="dot"];
/* next->prev = node; */
n1:se -> n0:p1:c [arrowtail="vee" arrowhead="dot"];
/* node->next = next; */
n1:p2:c -> n0:w;
/* node->prev = head; */
n1:p1:c -> n0:sw [weight="0"];
/* head->next = node; */
n1:ne -> n0:p2:c [color="orange" arrowtail="vee" arrowhead="dot"];
//{rank = same; new_node head; }
{rank = same; invis1 n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> n1 -> invis1 [weight="1"];
invis1 -> n0;
}
```
7.
> 變成
```graphviz
digraph circular_doubly_linked_list {
rankdir="LR";
head [shape="none"];
next [shape="none"];
new_node [shape="none", label="node"];
invis1 [shape="point" label="" style="invis"];
node [ shape="none", margin="0" label= <
<table color="blue" cellspacing="3" style="rounded" >
<tr>
<td color="black" port="p1" style="rounded" colspan="2">prev<br/> </td>
<td color="black" port="p2" style="rounded" colspan="2">next<br/> </td>
</tr>
</table>
>];
edge [arrowhead="vee" arrowtail="dot" dir="both" tailclip="false" headclip="false" arrowsize = "1" ]
/* draw head and struct list_head where head point to */
head:s -> n0:n [weight="0"];
/* draw node and struct list_head where node point to */
new_node:s -> n1:n [weight="0"];
/* struct list_head *next = head->next; */
n0:ne -> next:s [arrowtail="vee" arrowhead="dot" weight="0" color="grey"];
/* node->next = next; */
n1:p2:c -> n0:w [style="invis"];
n1:p2:c -> n0:w [weight="1"];
/* next->prev = node; */
n1:e -> n0:p1:c [arrowtail="vee" arrowhead="dot"];
n1:e -> n0:p1:c [arrowtail="vee" arrowhead="dot" style="invis"];
/* node->prev = head; */
n1:p1:c -> n0:sw [weight="0"];
/* head->next = node; */
n1:ne -> n0:p2:c [arrowtail="vee" arrowhead="dot"];
{rank = same; new_node n1; }
{rank = same; head n0; }
/* 'insivible' edge to adjust node placement */
edge [color="grey" style="invis"];
new_node -> head -> next [weight="1"];
}
```
:::danger
以 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。
:::
## 個人的想法
### 關於 git branch 的建立與命名方式
基於老師[投影片](https://docs.google.com/presentation/d/1xmb_mvsHISWp6naP1rHOyrxzMzNQkVoKK69lGRRXV9M/mobilepresent?slide=id.g4f2b7eb495_0_22)第 30 頁裡提到的 `Maslow's pyramid of code review` ，所以我在一開始的 `master` 的基準點額外建立以下 branch:
`executable`
`correct`
`secure`
`readable`
`elegent`
`altruist`
我在一開始連 `correct` 都做不到，所以額外建了 `executable`,然後針對 `queue.c` 以及其內部要實作的函式額外建立
`queue`
`queue_q_new`
`queue_q_size`
`queue_q_free`
`queue_q_insert_head`
`queue_q_insert_tail`...等
然後在 `queue.c` 撰寫程式碼，當某一個函式寫完能正常執行，然後只stash當前這個函式的程式碼再切換到對應的 branch，再 stash apply，commit，沒有問題之後再換回`queue`，再 merge 剛寫好的brach 的 commit。之後的打算是 `queue` 裡的函式都實作且可執行後，再 merge 到`executable`。<s>想請問這樣的過程有什麼地方需要改進嗎? 謝謝!</s>
:::warning
不要說「想請問這樣的過程有什麼地方需要改進嗎? 謝謝!」這種看似有禮貌，但實際資訊量不足的話。工程人員說話要精準，你該列出實際上的操作流程，而非詢問「心法」。列出詳盡過程，並提供初步檢討，這樣他人才可給你意見和交流。真誠地分享你的專業知識，讓溝通能夠達到共鳴，才是真正展現禮貌的方式。
:::
:::danger
詳閱 [Git 教學和 GitHub 設定指引](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2F%40sysprog%2Fgit-with-github)，裡頭的教學影片該細看。
:::
操作流程如下:
1. 想法是在 `queue.c` 的函式的實作過程中，每實作一個可運行的函式時就切換到對應的 `branch` (例如 `q_new()` ) 裡 `commit`，然後再切換到 `queue`，接著 `merge` 剛才的 `commit` 到 `queue`， **目的**是可以隨時**切換函式的某一次實作內容**。
2. 以當時 `fork` 的 `master branch`[(3aa0d55)](https://github.com/ihost1002/lab0-c/tree/3aa0d557fddd5fdd3ae5afb34f73a5c7be463e3c) 作為基準點，在 `terminal` 先確認當下在哪個 `branch`:
```shell
$ git branch
altruist
correct
elegent
executable
master
* queue
queue_debug
queue_q_free
queue_q_insert_head
queue_q_insert_tail
queue_q_new
queue_q_size
readable
secure
```
如果不是 `master` 就切換到 `master`:
```shell
$ git checkout master
```
3. 建立以下 `branch`:
3.1. `executable`
3.2. `correct`
3.3. `secure`
3.4. `readable`
3.5. `elegent`
3.6. `altruist`
3.7. `queue`
3.8. `queue_q_new`
3.9. `queue_q_free`
3.10. `queue_q_insert_head`
3.11. `queue_q_insert_tail`
3.12. `queue_q_size`
note: 上面顯示結果是已經建立各個 `branch`
```shell
$ git branch queue
$ git branck queue_q_new
$ ...
...依此類推
```
之後如果還要建立其他 `branch` 也是先切換到 `master` ， 目的是希望保持 `master` 乾淨，等到完成所有 `queue.c` 函式(測試執行沒有 `error`) 之後， `merge` 到 `executable` 裡，而目前 3.6 - 3.11 有實作內容並且已經 `push` 到自己 `fork` 的 `github repository` 裡，所以基本上如果別人看我的實作流程，只要看 `queue` 這個 `branch`。
3. 遇到錯誤且嘗試許久還是無法解決時，也是先切換到 `master` 建立且切換到 `queue_q_debug` ，然後 `merge` `queue`:
```shell
/* 假設當前在 'queue' branch */
$ git stash
$ git checkout master
$ git checkout -b queue_q_debug
$ git merge queue
$ git stash apply stash@{the desired one}
```
接著嘗試解決問題，如果解決了，就把解決後的結果 `commit` ， 在切換到 `queue` ， 再 `merge` `queue_q_debug`:
```shell
$ git checkout queue
$ git checkout merge queue_q_debug
```
**目的**是**重現**當時的問題
4. 目前開發紀錄 `commit`:
[queue](https://github.com/ihost1002/lab0-c/commits/queue/)
[queue_q_debug](https://github.com/ihost1002/lab0-c/commits/queue_debug)
[queue_q_new](https://github.com/ihost1002/lab0-c/commits/queue_q_new)
[queue_q_free](https://github.com/ihost1002/lab0-c/commits/queue_q_free)
[queue_q_insert_head](https://github.com/ihost1002/lab0-c/commits/queue_q_insert_head)
[queue_q_insert_tail](https://github.com/ihost1002/lab0-c/commits/queue_q_insert_tail)
[queue_q_size](https://github.com/ihost1002/lab0-c/commits/queue_q_size)
:::warning
以上分支的命名不直觀，應該先分類，例如 `wip/alloc` 分支包含 `q_new` 和 `q_free` 相關的變更 (可以是 2 個 commits)，接著是 `wip/insert`，包含 4 個相關函式 (可以是若干 commits，或集中一次 commit)。隨後可能會有 `refactor/insert` 或 `refactor/size` 這樣的變更，在不改變功能的前提，改進程式碼的可閱讀和可維護的程度。
:::
仔細思考了，老師提供的分支命名方式`簡潔易懂`，查詢了wip簡稱的意思:
wip: work in process (個人翻譯`建構中`)
另外 refactor:
來源: [refactor](https://en.wiktionary.org/wiki/refactor)
>(programming) To rewrite existing source code in order to improve its readability, reusability or structure without affecting its meaning or behaviour
>重寫程式碼，在不影響其意義或行為的情況下增進`可讀性`、`可利用性`或`程式結構`
而且把`功能相關`的`函式實作`用`一個分支`名稱來代表可減少分支數量，所以到這邊我先去細看 [queue.h](https://github.com/sysprog21/lab0-c/blob/master/queue.h) 每個`函式`的實作描述，才能把`功能相關`的`函式`分門別類，並把這些實作描述放在每個函式實作的開頭並加上個人解讀。
更新`分支`命名如下:
以 `wip/` 開頭後接 `6` 個分支名稱: `alloc`，`insert`，`size` ，`delete` ，`sort` ，`queue`。
`wip/alloc`:
此`分支`存放 `q_new()`， `q_free()` 兩個函式的 `commit`。
`wip/insert`:
此`分支`存放 `q_insert_head()`， `q_insert_tail()`，`q_remove_head()`， `q_remove_tail()` 四個函式的 `commit`。
`wip/size`:
此`分支`存放 `q_size()` 一個函式的 `commit`。
`wip/delete`:
此`分支`存放 `q_delete_mid()`， `q_delete_dup()` 兩個函式的 `commit`。
`wip/sort`:
此`分支`存放 `q_sort()`， `q_ascend()`，`q_descend()`， `q_swap()`， `q_reverse()`， `q_reverseK()` ，`q_merge()` 七個函式的 `commit`。
`wip/queue`:
此`分支`合併上述所有的 `commit`。等到 `16` 個函式都完成且經測試沒問題，再合併到 `master`。
後續有如老師說的『不改變功能的前提，改進程式碼的可閱讀和可維護的程度』的 `commit` 皆放在以 `refactor/` 開頭 加 上述分支對應名稱的分支，並且 `merge` 到 `master`。
另外，有仔細想過應該不需要為 `debug` 建立 `分支`，應該提出更正的 `commit`。
依照新的分支命名，刪除 `remote` 分支名稱:
`queue`
`queue_debug`
`queue_q_free`
`queue_q_insert_head`
`queue_q_insert_tail`
`queue_q_new`
`queue_q_size`
`terminal` 命令如下:
刪除 遠端 `queue` 分支:
```shell
$ git push origin --delete queue
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC dudect/constant.o
CC dudect/fixture.o
CC linenoise.o
CC web.o
LD qtest
Pre-push check passed!
To github.com:ihost1002/lab0-c
- [deleted] queue
```
看到這行:
> Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
發現 `remote url` (使用 `ssh`) 沒有改正確，下以下命令查看當前 `url`:
```shell
$ git remote -v
origin git@github.com:ihost1002/lab0-c (fetch)
origin git@github.com:ihost1002/lab0-c (push)
```
發現忘記加 `.git` (副檔名)，下以下命令修改 `url`:
```shell
$ git remote set-url origin git@github.com:ihost1002/lab0-c.git
```
重新確認 `url`:
```shell
$ git remote -v
origin git@github.com:ihost1002/lab0-c.git (fetch)
origin git@github.com:ihost1002/lab0-c.git (push)
```
刪除遠端 `queue_debug` 分支:
```shell
$ git push origin --delete queue_debug
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_debug
```
還是有 `hint`，好吧，那應該是本來就會有提示。
刪除遠端 `queue_q_free` 分支:
```shell
$ git push origin --delete queue_q_free
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_q_free
```
刪除遠端 `queue_q_insert_head` 分支:
```shell
$ git push origin --delete queue_q_insert_head
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_q_insert_head
```
刪除遠端 `queue_q_insert_tail` 分支:
```shell
$ git push origin --delete queue_q_insert_tail
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_q_insert_tail
```
刪除遠端 `queue_q_new` 分支:
```shell
$ git push origin --delete queue_q_new
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_q_new
```
刪除遠端 `queue_q_size` 分支:
```shell
$ git push origin --delete queue_q_size
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Running pre push to master check...
Trying to build tests project...
make: Nothing to be done for 'all'.
Pre-push check passed!
To github.com:ihost1002/lab0-c.git
- [deleted] queue_q_size
```
重新修改 `local` 分支:
新增 `wip/alloc` 分支:
```shell
$ git checkout master
$ git checkout -b wip/alloc
Switched to a new branch 'wip/alloc'
$ git branch
altruist
correct
elegent
executable
master
queue
queue_debug
queue_q_free
queue_q_insert_head
queue_q_insert_tail
queue_q_new
queue_q_size
readable
secure
* wip/alloc
```
修改 `queue_q_new` 分支的基準為 `wip/alloc`
```shell
$ git checkout queue_q_new
Switched to branch 'queue_q_new'
Your branch is based on 'origin/queue_q_new', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
// 切換前
$ git log -5 --oneline
a8ae197 (HEAD -> queue_q_new) Prevent NULL pointer in inline function
d8d6143 Initialize @prev @next with static inline function
9ca520c Implement q_new()
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
// 切換後
$ git rebase wip/alloc
Successfully rebased and updated refs/heads/queue_q_new.
$ git log -5 --oneline
6c80a7d (HEAD -> wip/alloc, origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
```
接著從 [Moving commits between branches](https://gist.github.com/unbracketed/889c844473bcca1917e2) 教學把 `queue_q_new` 底下的 3 個 `commit` 移動到 `wip/alloc`。
需要基準 `commit` (M)， 以及要移動的 `commits`，命令如下:
```shell
git checkout branch-B
git log # Note the SHA of most recent commit (M)
git rebase --onto M <commit before X> Y
git rebase HEAD branch-B
```
我的基準 `commit` (M) 為 `6c80a7d`
```shell
$ git checkout wip/alloc
Switched to branch 'wip/alloc'
ihost@ubuntu:~/linux2024/correct/lab0-c$ git log -5 --oneline
6c80a7d (HEAD -> wip/alloc, origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
```
要移動的 `commits` 來自 `queue_q_new`，從 `6cc373e` 到 `b20959c`:
```shell
$ git checkout queue_q_new
Switched to branch 'queue_q_new'
Your branch is based on 'origin/queue_q_new', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log --oneline
b20959c (HEAD -> queue_q_new) Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, wip/alloc, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
...
```
但 [Moving commits between branches](https://gist.github.com/unbracketed/889c844473bcca1917e2) 說到要前一個 `commit`，所以為 `6c80a7d`。過程如下:
```shell
$ git checkout wip/alloc
Switched to branch 'wip/alloc'
$ git log -5 --oneline
6c80a7d (HEAD -> wip/alloc, origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
$ git rebase --onto 6c80a7d 6c80a7d b20959c
Current branch b20959c is up to date.
$ git rebase HEAD wip/alloc
Current branch wip/alloc is up to date.
$ git log -5 --oneline
b20959c (HEAD -> wip/alloc, queue_q_new) Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
```
`queue_q_free` 分支比照辦理:
```shell
$ git checkout wip/alloc
Switched to branch 'wip/alloc'
$ git log -5 --oneline
b20959c (HEAD -> wip/alloc, queue_q_new) Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
$ git checkout queue_q_free
Switched to branch 'queue_q_free'
Your branch is based on 'origin/queue_q_free', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log -5 --oneline
fe46669 (HEAD -> queue_q_free) Executable of q_free()
ba700e9 Implement q_free()
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
b951eae Correct function parameter to match implementation
$ git checkout wip/alloc
Switched to branch 'wip/alloc'
$ git rebase --onto b20959c 3aa0d55 fe46669
Successfully rebased and updated detached HEAD.
$ git rebase HEAD wip/alloc
Successfully rebased and updated refs/heads/wip/alloc.
$ git log -5 --oneline
56a771c (HEAD -> wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c (queue_q_new) Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
```
最後 `push`:
```shell
$ git push -u origin wip/alloc
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Enumerating objects: 17, done.
Counting objects: 100% (17/17), done.
Delta compression using up to 6 threads
Compressing objects: 100% (15/15), done.
Writing objects: 100% (15/15), 2.21 KiB | 2.21 MiB/s, done.
Total 15 (delta 10), reused 0 (delta 0), pack-reused 0
remote: Resolving deltas: 100% (10/10), completed with 2 local objects.
remote:
remote: Create a pull request for 'wip/alloc' on GitHub by visiting:
remote: https://github.com/ihost1002/lab0-c/pull/new/wip/alloc
remote:
To github.com:ihost1002/lab0-c.git
* [new branch] wip/alloc -> wip/alloc
Branch 'wip/alloc' set up to track remote branch 'wip/alloc' from 'origin'.
```
刪除 `queue_q_new` `queue_q_free` 分支:
```shell
$ git branch -D queue_q_new
Deleted branch queue_q_new (was b20959c).
$ git branch -D queue_q_free
Deleted branch queue_q_free (was fe46669).
$ git log -10 --oneline
56a771c (HEAD -> wip/alloc, origin/wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
```
到 `master` 分支新增 `wip/insert`分支 並把 `queue_q_insert_head` `queue_q_insert_tail` 分支裡相關 `commits` 都移動到新分支:
```shell
$ git checkout master
Switched to branch 'master'
Your branch is up to date with 'origin/master'.
$ git checkout -b wip/insert
Switched to a new branch 'wip/insert'
$ git log -5 --oneline
6c80a7d (HEAD -> wip/insert, origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
$ git checkout queue_q_insert_head
Switched to branch 'queue_q_insert_head'
Your branch is based on 'origin/queue_q_insert_head', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log -5 --oneline
381d5d4 (HEAD -> queue_q_insert_head) Implement q_insert_head()
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
b951eae Correct function parameter to match implementation
34a821c Merge pull request #157 from komark06/master
$ git checkout wip/insert
Switched to branch 'wip/insert'
$ git rebase --onto 6c80a7d 3aa0d55 381d5d4
Successfully rebased and updated detached HEAD.
$ git rebase HEAD wip/insert
Successfully rebased and updated refs/heads/wip/insert.
$ git log -5 --oneline
ee90918 (HEAD -> wip/insert) Implement q_insert_head()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
$ git push -u origin wip/insert
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Enumerating objects: 5, done.
Counting objects: 100% (5/5), done.
Delta compression using up to 6 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 594 bytes | 594.00 KiB/s, done.
Total 3 (delta 2), reused 0 (delta 0), pack-reused 0
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
remote:
remote: Create a pull request for 'wip/insert' on GitHub by visiting:
remote: https://github.com/ihost1002/lab0-c/pull/new/wip/insert
remote:
To github.com:ihost1002/lab0-c.git
* [new branch] wip/insert -> wip/insert
Branch 'wip/insert' set up to track remote branch 'wip/insert' from 'origin'.
$ git checkout queue_q_insert_tail
Switched to branch 'queue_q_insert_tail'
Your branch is based on 'origin/queue_q_insert_tail', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log -5 --oneline
875af9e (HEAD -> queue_q_insert_tail) Implement q_insert_tail()
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
b951eae Correct function parameter to match implementation
34a821c Merge pull request #157 from komark06/master
$ git rebase --onto ee90918 3aa0d55 875af9e
Successfully rebased and updated detached HEAD.
$ git rebase HEAD wip/insert
Successfully rebased and updated refs/heads/wip/insert.
$ git log -5 --oneline
0623d11 (HEAD -> wip/insert) Implement q_insert_tail()
ee90918 (origin/wip/insert) Implement q_insert_head()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
$ git push -u origin wip/insert
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Enumerating objects: 5, done.
Counting objects: 100% (5/5), done.
Delta compression using up to 6 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 323 bytes | 323.00 KiB/s, done.
Total 3 (delta 2), reused 0 (delta 0), pack-reused 0
remote: Resolving deltas: 100% (2/2), completed with 2 local objects.
To github.com:ihost1002/lab0-c.git
ee90918..0623d11 wip/insert -> wip/insert
Branch 'wip/insert' set up to track remote branch 'wip/insert' from 'origin'.
$ git branch -D queue_q_insert_head
Deleted branch queue_q_insert_head (was 381d5d4).
$ git branch -D queue_q_insert_tail
Deleted branch queue_q_insert_tail (was 875af9e).
$ git branch
altruist
correct
elegent
executable
master
queue
queue_debug
queue_q_size
readable
secure
wip/alloc
* wip/insert
```
由於 `wip/size` 分支只有 `queue_q_size` 分支，所以使用「改變分支名稱」:
```shell
$ git checkout queue_q_size
Switched to branch 'queue_q_size'
Your branch is based on 'origin/queue_q_size', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git checkout master
Switched to branch 'master'
Your branch is up to date with 'origin/master'.
$ git branch -m queue_q_size wip/size
$ git branch
altruist
correct
elegent
executable
* master
queue
queue_debug
readable
secure
wip/alloc
wip/insert
wip/size
$ git checkout wip/size
Switched to branch 'wip/size'
Your branch is based on 'origin/queue_q_size', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log -5 --oneline
5ead6ce (HEAD -> wip/size) Correct coding style to make it consistent
af88158 Implement q_size()
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
b951eae Correct function parameter to match implementation
$ git rebase master
Successfully rebased and updated refs/heads/wip/size.
$ git log -5 --oneline
2be628e (HEAD -> wip/size) Correct coding style to make it consistent
3c6484e Implement q_size()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
$ git push -u origin wip/size
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Enumerating objects: 8, done.
Counting objects: 100% (8/8), done.
Delta compression using up to 6 threads
Compressing objects: 100% (6/6), done.
Writing objects: 100% (6/6), 849 bytes | 849.00 KiB/s, done.
Total 6 (delta 4), reused 0 (delta 0), pack-reused 0
remote: Resolving deltas: 100% (4/4), completed with 2 local objects.
remote:
remote: Create a pull request for 'wip/size' on GitHub by visiting:
remote: https://github.com/ihost1002/lab0-c/pull/new/wip/size
remote:
To github.com:ihost1002/lab0-c.git
* [new branch] wip/size -> wip/size
Branch 'wip/size' set up to track remote branch 'wip/size' from 'origin'.
```
再來換 `queue`分支:
```shell
$ git checkout queue
Switched to branch 'queue'
Your branch is based on 'origin/queue', but the upstream is gone.
(use "git branch --unset-upstream" to fixup)
$ git log -20 --oneline
dc78c0a (HEAD -> queue) Executable of q_free()
85203f7 Implement q_insert_tail()
f5c7c17 Implement q_insert_head()
3976c68 Correct coding style to make it consistent
fb6cff3 Prevent NULL pointer in inline function
5462a14 Implement q_free()
7cbc729 Implement q_size()
1347078 Initialize @prev @next with static inline function
29e4c31 Implement q_new()
6d10163 Suppress Cppcheck constant check (#154)
f033695 Correct function parameter to match implementation
cc84763 Fix typo
19a3e70 Fix cppcheck failed since after version 2.9
dbfa430 Fix pre-push.hook validation bug
b64d2fc Apply shell annotation
d03c42a Adjust the range for pre-push git hook
3ed1723 Bump copyright year
1aca5b9 Merge pull request #149 from sysprog21/ci-check-newline
4ee18d7 Enforce newline at end of files
844d107 Enforce grep -E instead of egrep
$ git rebase master
warning: skipped previously applied commit dbfa430
warning: skipped previously applied commit 19a3e70
warning: skipped previously applied commit cc84763
warning: skipped previously applied commit f033695
warning: skipped previously applied commit 6d10163
hint: use --reapply-cherry-picks to include skipped commits
hint: Disable this message with "git config advice.skippedCherryPicks false"
Successfully rebased and updated refs/heads/queue.
$ git log -30 --oneline
830db73 (HEAD -> queue) Executable of q_free()
377955f Implement q_insert_tail()
ee7a986 Implement q_insert_head()
b34e262 Correct coding style to make it consistent
7e60bb9 Prevent NULL pointer in inline function
7485e9f Implement q_free()
c6fd76b Implement q_size()
b190bed Initialize @prev @next with static inline function
5f78e6b Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
b13335b Introduce eventmux callback function for linenoise
39c85e9 Merge pull request #163 from 25077667/master
cec5179 Suppress Cppcheck checking level
3aa0d55 (secure, readable, executable, elegent, correct, altruist) Suppress Cppcheck constant check (#154)
bbd4243 Merge pull request #159 from komark06/master
b951eae Correct function parameter to match implementation
34a821c Merge pull request #157 from komark06/master
b6de2ed Fix typo
267cca7 Fix cppcheck failed since after version 2.9
4627f69 Merge pull request #152 from vax-r/Fix_pre_push_hook_bug
9fa4d90 Fix pre-push.hook validation bug
390ade9 Merge pull request #150 from sysprog21/bump-copyright-year
b64d2fc Apply shell annotation
d03c42a Adjust the range for pre-push git hook
3ed1723 Bump copyright year
1aca5b9 Merge pull request #149 from sysprog21/ci-check-newline
```
`rebase` 過程中出現 `warning`， 使用 `hint` 提到的 `--reapply-cherry-picks`:
```shell
$ git rebase --reapply-cherry-picks dbfa430
dropping 9fa4d904738e8306544998bf41def65368f90683 Fix pre-push.hook validation bug -- patch contents already upstream
Successfully rebased and updated refs/heads/queue.
$ git rebase --reapply-cherry-picks 19a3e70
dropping 0bc78553d27276373a5bce18a32e2a22040e1948 Fix cppcheck failed since after version 2.9 -- patch contents already upstream
Successfully rebased and updated refs/heads/queue.
$ git rebase --reapply-cherry-picks cc84763
dropping 9e48417aec8d711568f5ae191ba39f813ee0a085 Fix typo -- patch contents already upstream
Successfully rebased and updated refs/heads/queue.
$ git rebase --reapply-cherry-picks f033695
dropping b76bbb47f72289514ee99601f0f47a9894605197 Correct function parameter to match implementation -- patch contents already upstream
Successfully rebased and updated refs/heads/queue.
$ git rebase --reapply-cherry-picks 6d10163
dropping b9bd5c9d9174bc9b4be074063608ed4ebe82c1cf Suppress Cppcheck constant check (#154) -- patch contents already upstream
Successfully rebased and updated refs/heads/queue.
$ git log -30 --oneline
35f9d2d (HEAD -> queue) Executable of q_free()
8699631 Implement q_insert_tail()
1c3466c Implement q_insert_head()
451b962 Correct coding style to make it consistent
c6dcea6 Prevent NULL pointer in inline function
8c84627 Implement q_free()
3a820c9 Implement q_size()
1f0bcde Initialize @prev @next with static inline function
f55e1a4 Implement q_new()
1ea41d8 Fix typo (#171)
00e8f4b Fix typo (#169)
8ebbf60 Enforce newline at the end of files
df99c88 Introduce eventmux callback function for linenoise
d0ba78e Suppress Cppcheck checking level
6d10163 Suppress Cppcheck constant check (#154)
f033695 Correct function parameter to match implementation
cc84763 Fix typo
19a3e70 Fix cppcheck failed since after version 2.9
dbfa430 Fix pre-push.hook validation bug
b64d2fc Apply shell annotation
d03c42a Adjust the range for pre-push git hook
3ed1723 Bump copyright year
1aca5b9 Merge pull request #149 from sysprog21/ci-check-newline
4ee18d7 Enforce newline at end of files
844d107 Enforce grep -E instead of egrep
2b55930 Refine contributing guide
f89795d Merge pull request #148 from sysprog21/prefer-kirby
406e36b Prefer Kirby
be86d0f Merge pull request #146 from sysprog21/revert-145-dedup_bug
b900e2d Revert "Fix duplicate item detection issue"
```
沒看到 `master` 分支，想了想，乾脆砍掉重作好了:
```shell
$ git checkout master
Switched to branch 'master'
Your branch is up to date with 'origin/master'.
$ git branch -D queue
Deleted branch queue (was 35f9d2d).
$ git checkout -b wip/queue
Switched to a new branch 'wip/queue'
$ git merge wip/alloc
Updating 6c80a7d..56a771c
Fast-forward
queue.c | 33 +++++++++++++++++++++++++++++++--
1 file changed, 31 insertions(+), 2 deletions(-)
$ git log -10 --oneline
56a771c (HEAD -> wip/queue, origin/wip/alloc, wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
$ git merge wip/insert
Auto-merging queue.c
Merge branch 'wip/insert' into 'wip/queue' [line 1]
- Possible misspelled word(s): wip
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
Proceed with commit? [e/n/?] n
Not committing merge; use 'git commit' to complete the merge.
$ git st
On branch wip/queue
All conflicts fixed but you are still merging.
(use "git commit" to conclude merge)
Changes to be committed:
modified: queue.c
$ git stash
Saved working directory and index state WIP on queue: 56a771c Executable of q_free()
$ git stash drop stash@{0}
Dropped stash@{0} (ecae84e61206537b168e3560321ed5043c80e8aa)
```
`merge` `wip/insert` 的時候 `pre-commit hook` 檢查拼字發現 `wip` 不是正確的單字，這時我改成 `git rebase`:
```shell
$ git checkout wip/insert
Switched to branch 'wip/insert'
Your branch is up to date with 'origin/wip/insert'.
$ git log -10 --oneline
0623d11 (HEAD -> wip/insert, origin/wip/insert) Implement q_insert_tail()
ee90918 Implement q_insert_head()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
5d1b7f1 Enforce newline at the end of files
dd6a761 Merge pull request #162 from vax-r/Integrate_linenoise_web
b13335b Introduce eventmux callback function for linenoise
39c85e9 Merge pull request #163 from 25077667/master
cec5179 Suppress Cppcheck checking level
$ git checkout wip/queue
Switched to branch 'wip/queue'
$ git rebase --onto 56a771c 6c80a7d 0623d11
Successfully rebased and updated detached HEAD.
$ git rebase HEAD wip/queue
Successfully rebased and updated refs/heads/wip/queue.
$ git log -10 --oneline
a6d3a41 (HEAD -> wip/queue) Implement q_insert_tail()
0e3778b Implement q_insert_head()
56a771c (origin/wip/alloc, wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
$ git st
On branch wip/queue
nothing to commit, working tree clean
```
`merge` `wip/size` 也發生相同問題，也改用 `git rebase`:
```shell
$ git merge wip/size
Auto-merging queue.c
Merge branch 'wip/size' into wip/queue [line 1]
- Possible misspelled word(s): wip
How to Write a Git Commit Message: https://chris.beams.io/posts/git-commit/
Proceed with commit? [e/n/?] n
Not committing merge; use 'git commit' to complete the merge.
$ git st
On branch wip/queue
All conflicts fixed but you are still merging.
(use "git commit" to conclude merge)
Changes to be committed:
modified: queue.c
$ git stash
Saved working directory and index state WIP on queue: a6d3a41 Implement q_insert_tail()
$ git stash list
stash@{0}: WIP on queue: a6d3a41 Implement q_insert_tail()
$ git stash drop stash@{0}
Dropped stash@{0} (07972bb8e185e8be52e9c4cfebef8fafaf26561a)
$ git checkout wip/size
Switched to branch 'wip/size'
Your branch is up to date with 'origin/wip/size'.
$ git log -5 --oneline
2be628e (HEAD -> wip/size, origin/wip/size) Correct coding style to make it consistent
3c6484e Implement q_size()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
$ git checkout wip/queue
Switched to branch 'wip/queue'
$ git log -10 --oneline
a6d3a41 (HEAD -> wip/queue) Implement q_insert_tail()
0e3778b Implement q_insert_head()
56a771c (origin/wip/alloc, wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
b1fbeb7 Fix typo (#169)
5dcb1bd Merge pull request #166 from visitorckw/enforce-newline
$ git rebase --onto a6d3a41 6c80a7d 2be628e
Successfully rebased and updated detached HEAD.
$ git rebase HEAD wip/queue
Successfully rebased and updated refs/heads/wip/queue.
$ git log -10 --oneline
c311a31 (HEAD -> wip/queue) Correct coding style to make it consistent
7fdbe1f Implement q_size()
a6d3a41 Implement q_insert_tail()
0e3778b Implement q_insert_head()
56a771c (origin/wip/alloc, wip/alloc) Executable of q_free()
19af247 Implement q_free()
b20959c Prevent NULL pointer in inline function
23e456b Initialize @prev @next with static inline function
6cc373e Implement q_new()
6c80a7d (origin/master, origin/HEAD, master) Fix typo (#171)
```
順便檢查當前 `wip/queue` 最新 `commit` 狀態:
```shell
$ git st
On branch wip/queue
nothing to commit, working tree clean
$ make
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC dudect/constant.o
CC dudect/fixture.o
CC linenoise.o
CC web.o
LD qtest
$ make check
./qtest -v 3 -f traces/trace-eg.cmd
cmd> # Demonstration of queue testing framework
cmd> # Use help command to see list of commands and options
cmd> # Initial queue is NULL.
cmd> show
l = NULL
cmd> # Create empty queue
cmd> new
l = []
cmd> # See how long it is
cmd> size
Queue size = 0
l = []
cmd> # Fill it with some values. First at the head
cmd> ih dolphin
l = [dolphin]
cmd> ih bear
l = [bear dolphin]
cmd> ih gerbil
l = [gerbil bear dolphin]
cmd> # Now at the tail
cmd> it meerkat
l = [gerbil bear dolphin meerkat]
cmd> it bear
l = [gerbil bear dolphin meerkat bear]
cmd> # Reverse it
cmd> reverse
l = [gerbil bear dolphin meerkat bear]
cmd> # See how long it is
cmd> size
Queue size = 5
l = [gerbil bear dolphin meerkat bear]
cmd> # Delete queue. Goes back to a NULL queue.
cmd> free
l = NULL
cmd> # Exit program
cmd> quit
Freeing queue
```
沒問題，接著 `push`:
```shell
$ git push -u origin wip/queue
Hint: You might want to know why Git is always asking for my password.
https://docs.github.com/en/get-started/getting-started-with-git/why-is-git-always-asking-for-my-password
Enumerating objects: 14, done.
Counting objects: 100% (14/14), done.
Delta compression using up to 6 threads
Compressing objects: 100% (12/12), done.
Writing objects: 100% (12/12), 1.62 KiB | 1.62 MiB/s, done.
Total 12 (delta 8), reused 0 (delta 0), pack-reused 0
remote: Resolving deltas: 100% (8/8), completed with 2 local objects.
remote:
remote: Create a pull request for 'wip/queue' on GitHub by visiting:
remote: https://github.com/ihost1002/lab0-c/pull/new/wip/queue
remote:
To github.com:ihost1002/lab0-c.git
* [new branch] wip/queue -> wip/queue
Branch 'wip/queue' set up to track remote branch 'wip/queue' from 'origin'.
```
刪除 `queue_debug`，`altruist`，`correct`，`elegent`，`executable`，`readable`，`secure`:
```shell
$ git branch -D queue_debug
Deleted branch queue_debug (was 76de14b).
$ git branch -D altruist
Deleted branch altruist (was 3aa0d55).
$ git branch -D correct
Deleted branch correct (was 3aa0d55).
$ git branch -D elegent
Deleted branch elegent (was 3aa0d55).
$ git branch -D executable
Deleted branch executable (was 3aa0d55).
$ git branch -D readable
Deleted branch readable (was 3aa0d55).
$ git branch -D secure
Deleted branch secure (was 3aa0d55).
```
新增 `wip/delete` `wip/sort` 分支:
```shell
$ git branch wip/delete
$ git branch wip/sort
$ git branch
* master
wip/alloc
wip/delete
wip/insert
wip/queue
wip/size
wip/sort
```
目前 `wip/delete` `wip/sort` 分支還沒有新的commit，所以更新後的開發紀錄 `commits`:
[wip/alloc](https://github.com/ihost1002/lab0-c/commits/wip/alloc/)
[wip/insert](https://github.com/ihost1002/lab0-c/commits/wip/insert/)
[wip/queue](https://github.com/ihost1002/lab0-c/commits/wip/queue/)
[wip/size](https://github.com/ihost1002/lab0-c/commits/wip/size/)
### git 與 github 開發紀錄
1. 由於 `wip/queue` 是由 `wip/*` 這些分支的 `commits` 組成，從後者 `merge` 到前者的過程中， `pre-commit hook` 可能會阻擋，例如不對的拼字 `wip`， 所以都改成 `git rebase`， 但是看 [Git 教學系列 - rebase](https://youtu.be/0nwqar3ycTY?si=hiuga2gadqij1pds) 之後才知道，雖然這些 `git rebase` 的 `commit message` 跟之前的 `commit` 訊息一樣，但是 `hash` 與原先是不同的，所以覺得有必要告知兩者是相同的，於是在 `wip/queue` 的 `commits` 都在描述裡寫道其對應的是哪一個分支的 `commit`，使用命令 `git rebase -i HEAD[^]` ， `^` 數量對應要編輯的 `commit`。但後來想了想，我建立這個分支的目的是合併所有 `wip/*` 的 `commits`，最後在 `master` 整合成一個可執行 `queue.c` 所有函式的 `commit`，所以特別指出某個 `commit` 從哪個分支過來好像也沒有必要，因為 `commit message` 相同。
2. 從 3/10 到近幾天 `master` 有更新，所以把所有分支都 `sync` 到最新，但發現預設使用 `merge` 方式會打亂原本的 `commit` 順序，因此讓我想到既然可以 `reset` `local commit`，那是否可以 `reset` `remote commit`，因此去閱讀 `git` 文件。查了 [git reset]() 和 [git push]() 試著理解應該使用哪個選項，最後還是不甚瞭解，只好google了，找到 [how-to-delete-commits-from-remote-in-git](https://hackernoon.com/how-to-delete-commits-from-remote-in-git) 終於知道要使用命令:
`git push origin HEAD --force`
但要先把 `local` 分支改成自己要的樣子，過程大致如下(以 `wip/insert` 為例):
```shell
$ git checkout wip/insert
$ git reset HEAD^^^^^ --hard
$ git checkout d798d90a5117502b75a5469ad1770edcea045ffb
$ git rebase HEAD wip/insert
```
其他分支以相似方式處理。而我這時發現，上個段落提到在 `wip/queue` 每個 `rebase` 過來的 `commit` 由於都有加上對應的 `hash` ， 所以我可以 `git checkout` 到對應的 `commit`， 也幸好這些 `commit` 還沒被 `git` 回收。也提醒自己:
* 如 [Git 教學系列 - rebase](https://youtu.be/0nwqar3ycTY?si=hiuga2gadqij1pds) 說到的，要先建立 `backup` 分支，如果出問題的話也不影響到原來的，經歷這件事後深有體會。
* 也在思考如何更謹慎的寫好每一個 `commit`，因為一旦這個 `commit` 是公開且別人有參與的話，根本就不能隨便亂改。
繼續研究 [Git 教學系列 - Remote and Github](https://youtu.be/ucOqDIrV95s?si=f-5WA1jqrtsUImpy)。
## 疑問
### 課內的疑問
:::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)
:::
1. 實作 `q_new` 的時候，一開始我自己忘記對 `prev` 及 `next` 初始化，導致 `make check` 的時候在 `new` 時顯示錯誤，我知道應該要初始化，但我好奇的是哪一個 函式 來檢查沒有初始化並且顯示錯誤訊息,猜測可能在 `qtest.c` 裡面但作業還沒寫完就先擱置了。
2. 存檔的時候出現的紅色警告，訊息如下:
> Error detected while processing BufWrite Autocommands for "*.c"..function Formatonsave: line 2: Traceback (most recent call last):
File "string", line 1, in "queue.c" 116L, 2787B written
:::danger
文字訊息請避免用圖片來表示，否則不好搜尋和分類
:::
這個找到了，原來是
```script
By adding the following into $HOME/.vimrc
function! Formatonsave()
let l:formatdiff = 1
py3f <path-to-clang-format.py>/clang-format.py
endfunction
autocmd BufWritePre *.h,*.hpp,*.c,*.cc,*.cpp call Formatonsave()
```
這邊的 `<path-to-clang-format.py>` 沒改到，改成 `clang-format.py` 檔案的路徑就解決了! 而我的路徑剛好為 `/usr/share/vim/addons/syntax/`
3. 原始程式碼也許可以改進的部分
```
$ git commit -a
Following files need to be cleaned up:
queue.c
queue.h
/usr/bin/sha1sum: WARNING: 1 computed checksum did NOT match
[!] You are not allowed to change the header file queue.h or list.h
```
在 `queue.c` 裡的 `q_size` 的 function 宣告為:
```c
int q_size(struct list_head *head)
{
}
```
這個參數是不是可以改成 `const list_head *head`? 因為累計 `node` 個數的過程不應該修改 `head` 或是其中任何 `node` 的內容，我那時候想說這樣改應該比較好所以也去改對應的 `queue.h` ，直到 `pre-commit hook` 檢查後顯示不應該去改，但改成 `const list_head *head` 應該是比較安全的作法
4. pre-commit hook
```diff
/* Free all storage used by queue */
-void q_free(struct list_head *head) {
+void q_free(struct list_head *head)
+{
if (!head)
return ;
if (list_empty(head)) {
[!] queue.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i queue.c
Following files need to be cleaned up:
queue.c
```
在初始 `fork` `lab0-c` 後，`void q_free()` 其後面接的 {} 應該從下一行開頭，那為什麼直接接在 () 後面且裡面沒有任何內容的時候 commit 會過？
5. 如果使用 `puts`、`sprintf`、`strcpy` 會有風險，那為什麼沒有人要幫忙修改裡面的實作內容讓其變為無風險呢?
6. `qtest` 裡的佇列名稱仍然是 `l` 不是 `q` ，我先擱著，等其他 函式 寫完可執行之後再來找這個問題
:::danger
沒有所謂的「課外」，只要讓你的專業素養變強，都算是課程的範疇。
:::
7. 其實有這想法是源自[投影片](https://docs.google.com/presentation/d/1xmb_mvsHISWp6naP1rHOyrxzMzNQkVoKK69lGRRXV9M/mobilepresent?slide=id.g207f77d4362_0_427) 第 48 頁說到的，有辦法自建才真的懂，所以就想到該如何完全不借助任何 `C` 內建的功能，內建的 `funcion` 或 `macro` 都不使用，而是自己建立適當的 `macro` 或 函式，從頭到尾自建一個 `printf` 函式 ，我大概知道要用到 `va_list`, `va_start`, `va_arg`, `va_end` ，但我還是無法實作跟這些`macro`相同的功能，所以其實我不懂 ; 另外我曾經嘗試自己看 `gnu` 的 `source code` ，但是從 `stdio.h` 這個 `header` 進去研究之後，跟著 `macro` 定義跳來跳去，跳到最後都不知道自己看到哪了，<s>想請問各位高手要從哪裡切入會比較有可能實際了解並實作出來? 如果方便的話歡迎提供參考的資料，我會自己先看，研究很久看不懂再請教，感謝各位！</s>
:::danger
不要說「請問各位高手..」，你應該清楚闡述，若問題能引來共鳴，自然會有人回覆你，否則你只是堆砌無助於專業討論的詞彙。
:::
> 首先你該閱讀第一手材料，例如 C 語言規格書，清楚知道行為，才有辦法實作。現行的資訊教育往往造就一堆眼高手低的學員 (授課教師可能也是這樣的人，不全然是學生的錯)，後者追求用短時間給出「正確」的答案，於是初步的程式碼出現後，就沒有後續 (就像台灣媒體喜歡說「AI 元年」一類的詞彙，請問第二年和第十年在哪？)。動手！
>
> 留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
> :notes: jserv
> 感謝老師花時間批改，我會注意盡量不要用到非必要的縮排，您提到的中英文字中間要間隔大致已修改 (可能眼花漏掉)，文字訊息的圖片也都附上文字，Mark Down、Graphviz 、「Git 教學和 GitHub 設定指引」 跟 C 語言規格書 我去研究，感恩!
Sign in with Wallet
Connect another wallet