Try   HackMD

2024q1 Homework1 (lab0)

contributed by < ihost1002 >

開發環境

$ 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 語言規格書

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

C99 ( ISO/IEC 9899:1999 ): N1256 、 1999
Note : 上面第一個參考來自你所不知道的C語言：開發工具和規格標準，第二個參考是自google搜尋到的，在課程討論區感謝 Niclas3 同學的回覆，個人理解後應該是 N1256 版本較新，所以後來查找資料都以 N1256 為主
Niclas 同學的回覆如下（時間為2024/2/19):

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →


文字內容:
Niclas3 (Niclas) : TC 应该是技术勘误的意思，
https://www.open-std.org/jtc1/sc22/wg14/www/standards.html#9899 这里是我找到的相关网页
Niclas3 (Niclas) : n1507 应该是 C11 的文档版本号。C99 经过3次修订所以最终草稿应该是 TC3 。我一开始提供的文档是一个草稿文档， ihost1002 给的应该是 iSO 的正式版文档，我查到的资料看来两者没有内容上的区别。如有遗漏还望指正

文字訊息請避免用圖片來表示，否則不好搜尋和分類。

針對佇列操作的程式碼實作

q_size

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

  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

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

詳細內容：make check結果與lab0頁面一開始的結果不同，lab0頁面如下：
參閱 lab0-c 的文件 (即 README.md 檔案) 後，我們得知能用以下命令測試 qtest:

$ 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

避免贅詞。

而我自己的結果如下：

$ 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)

不要濫用 :::info 一類的標注，內容才是關鍵！

因此想要找出問題點，由上可知以下差異

  1. 在新增queue的時候沒有成功，仍顯示 NULL
  2. 在輸入size的時候出現錯誤
  3. queue的名稱為 l ，而 lab0 顯示的queue名稱為 q

command 的翻譯是「命令」，而非「指令」

因為沒有認真看題目敘述，所以試著自己尋找這個錯誤是從哪裡出現的，而 qtest 是由許多個 .o 執行檔組合而成，因此先在 linux cmd 執行命令
$ ./qtest
進到 cmd > ,試著打 help 找到命令 size ,顯示為回傳 queue 的 size ,然後又看了 new 是新增一個 queue ,因此猜測出錯的 source 檔案可能為跟處理 queue 有關，下了命令
$ ls *.c

command 的翻譯是「命令」，而非「指令」

找到最有可能的檔案為 queue.c ,用 vim 打開，找到

/* 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 的第 18 到 38 行找到它的宣告如下：

/**
 * 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 。
目前完成結果如下：

/* 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;
}

避免贅詞。

以下是我的作法：

  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 檢查，所以馬上更正。

/* 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

為何不閱讀第一手材料呢？

q_new

/**
 * 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 第 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 第 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。

程式碼如下:

/* 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

/**
 * 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 時在 commit 04cf2c6 看到註解寫到 strcpy 是不安全的函式，而後來再搜尋一次關鍵字 strcpy 時找到 lab0-c/scripts
/pre-commit.hook ，所以 commit 的時候 pre-commit hook 會檢查如果使用這幾個 function 就不會過，提醒自己記得不要使用 gets、sprintf、strcpy，所以在複製字串到 element_t 裡的 valuemember 的功能可改用 strncpy 。接著我一直在想 struct list_head * 類型跟 element_t * 不同啊！不能把前者指向後者啊，可是 lab0-c/queue.h 第58行清楚說道要 Insert an element in the head ，這邊卡了應該有半天，後來真的想不出辦法，就去看 2023 年其他同學的寫法，感謝 25077667 同學提交的作業資料，當看到這一行的的時候:

    op(&me->list, head);

終於了解原來 insert 是指 element_t 的成員 list 而且要轉成struct list_head * ，而且同學使用 helper function 及 pointer to a function 來避免重複的程式碼真是太棒了! 但後來想想畢竟不是我自己想到的，所以我還是先自己寫看看。一開始程式碼如下:

/* 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 。程式碼如下:

/* 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

/**
 * 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 比照辦理，程式碼如下:

/* 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 第 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

/**
 * 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 不造成任何影響。

初始程式碼:

/* 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);
}

執行結果:

$ 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()，第 67 到 86 行。

完成的程式碼:

/* 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);
}

$ 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

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。如果 @sp 不是 NULL 且 element 即 element_t * 已被 remove， 則從 element_t->value 複製 bufsize-1 個字元 及結尾 \⍬ 到 @sp。所以可理解為只要複製不需要再 alloacate。

這邊寫出來了，還在整理。

q_remove_tail

/**
 * 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 第 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

/**
 * 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

/**
 * 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

/**
 * 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

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。這個函式不該額外 allocate 或 free 任何 element_t，即不使用 q_insert_*、 q_remove_*、 q_delete_* 等相關功能的函式。只有重新排列既存節點的順序。

q_reverseK

/**
 * 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 第 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

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。

如何確保目前的測試已涵蓋排序演算法的最差狀況？

老師，對不起 ，之前用留言回覆，現在改在您留言底下回覆，請問您的意思是在完成 q_new、 q_size、q_free、q_insert_head、q_insert_tail 後先考慮測試是否涵蓋排序演算法的最差狀況，例如說要遞增排序但是當前的佇列是遞減排序嗎？

不用跟我道歉，你唯一需要道歉的理由是「你不夠強」。參閱 2024-03-{05,07,12} 問答紀錄

q_ascend

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。回傳經此函式運算後剩下的節點個數。remove 與 delete 的差別參考 q_remove_head。舉例: "abc", "bc", "A", "cd", "C" 經 q_ascend() 結果為 "A", "C"，回傳 2。

q_descend

/**
 * 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 第 161 - 170 行 list_empty，即 佇列 的成員 @prev 及 @next 皆指向佇列本身。回傳經此函式運算後剩下的節點數。remove 與 delete 的差別參考 q_remove_head。舉例: "abc", "bc", "z", "cd", "d" 經 q_descend() 結果為 "z", "d"，回傳 2。

q_merge

/**
 * 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 第 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 設定指引。

修正自己的錯誤認知

list_add

來源: lab0-c/list.h 第88-101行
程式碼:

/**
 * 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;
}

原來以為是這樣，但是是錯的：

head 和 node







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






new_node
node




n1

prev
 

next
 




new_node:e->n1:w








n0:c->n0:w






n0:c->n0:e







n1:c->n1:w






n1:c->n1:e

struct list_head *next = head->next;
錯在這邊， next 應指向 head，不是指向另一個 node







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node




n1

prev
 

next
 




new_node:e->n1:w










n0:c->n0:w






n0:c->n0:e






n0:c->n2:w







n1:c->n1:w






n1:c->n1:e

next->prev = node;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node




n1

prev
 

next
 




new_node:e->n1:w










n0:c->n0:w






n0:c->n2:w







n1:c->n1:w






n1:c->n1:e






n2:c->n1:se

node->next = next;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node




n1

prev
 

next
 




new_node:e->n1:w










n0:c->n0:w






n0:c->n2:w







n1:c->n1:w






n1:c->n1:e






n1:c->n2:nw






n2:c->n1:se

node->prev = head;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node




n1

prev
 

next
 




new_node:e->n1:w










n0:c->n0:w






n0:c->n2:w







n1:c->n0:e






n1:c->n1:w






n1:c->n2:nw






n2:c->n1:se

head->next = node;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node




n1

prev
 

next
 




new_node:e->n1:w










n0:c->n0:w






n0:c->n1:w






n0:c->n2:w







n1:c->n0:e






n1:c->n2:nw






n2:c->n1:se

變成







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



n2

prev
 

next
 




next:e->n2:sw






new_node
node



n1

prev
 

next
 




new_node:e->n1:sw






n0:c->n0:w







n0:c->n1:w







n1:c->n0:e








n1:c->n2:w







n2:c->n1:e

正確的：

head 和 node







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






new_node
node




n1

prev
 

next
 




new_node:e->n1:w








n0:c->n0:w






n0:c->n0:e







n1:c->n1:w






n1:c->n1:e

struct list_head *next = head->next;
next 指向 head







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



next:e->n0:sw






new_node
node



n1

prev
 

next
 




new_node:e->n1:w









n0:c->n0:w






n0:c->n0:e







n1:c->n1:w






n1:c->n1:e

next->prev = node;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



next:e->n0:sw






new_node
node



n1

prev
 

next
 




new_node:e->n1:w









n0:c->n0:w






n0:c->n0:e







n1:se->n0:c






n1:c->n1:w






n1:c->n1:e

node->next = next;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:w






next
next



next:e->n0:sw






new_node
node



n1

prev
 

next
 




new_node:e->n1:w









n0:c->n0:e







n1:se->n0:c






n1:c->n0:nw






n1:c->n1:w






n1:c->n1:e

node->prev = head;







circular_doubly_linked_list



head
head



n0

prev
 

next
 




head:e->n0:s






next
next



next:e->n0:se






new_node
node



n1

prev
 

next
 




new_node:e->n1:w









n0:c->n0:e







n1:se->n0:c






n1:c->n0:w






n1:c->n0:sw






n1:c->n1:w

head->next = node;







circular_doubly_linked_list



head
head



next
next



new_node
node



n1

prev
 

next
 




new_node:e->n1:w








n0

prev
 

next
 





n0:s->head:w






n0:se->next:w






n0:c->n0:e







n1:se->n0:c






n1:c->n0:w






n1:c->n0:sw






n1:ne->n0:c

變成







circular_doubly_linked_list



head
head



next
next




n0

prev
 

next
 




head:s->n0:n





new_node
node




n1

prev
 

next
 




new_node:s->n1:n






n0:ne->next:s







n1:c->n0:w






n1:e->n0:c







n1:c->n0:sw






n1:ne->n0:c

以 Graphviz 重新製圖，並嵌入到 HackMD 筆記中。

個人的想法

關於 git branch 的建立與命名方式

基於老師投影片第 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。想請問這樣的過程有什麼地方需要改進嗎? 謝謝!

不要說「想請問這樣的過程有什麼地方需要改進嗎? 謝謝!」這種看似有禮貌，但實際資訊量不足的話。工程人員說話要精準，你該列出實際上的操作流程，而非詢問「心法」。列出詳盡過程，並提供初步檢討，這樣他人才可給你意見和交流。真誠地分享你的專業知識，讓溝通能夠達到共鳴，才是真正展現禮貌的方式。

詳閱 Git 教學和 GitHub 設定指引，裡頭的教學影片該細看。

操作流程如下:

  1. 想法是在 queue.c 的函式的實作過程中，每實作一個可運行的函式時就切換到對應的 branch (例如 q_new() ) 裡 commit，然後再切換到 queue，接著 merge 剛才的 commit 到 queue， 目的是可以隨時切換函式的某一次實作內容。
  2. 以當時 fork 的 master branch(3aa0d55) 作為基準點，在 terminal 先確認當下在哪個 branch:
$ 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:

$ git checkout master
  1. 建立以下 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
$ 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。

  1. 遇到錯誤且嘗試許久還是無法解決時，也是先切換到 master 建立且切換到 queue_q_debug ，然後 merge queue:
/* 假設當前在 '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:

$ git checkout queue
$ git checkout merge queue_q_debug

目的是重現當時的問題

  1. 目前開發紀錄 commit:
    queue
    queue_q_debug
    queue_q_new
    queue_q_free
    queue_q_insert_head
    queue_q_insert_tail
    queue_q_size

以上分支的命名不直觀，應該先分類，例如 wip/alloc 分支包含 q_new 和 q_free 相關的變更 (可以是 2 個 commits)，接著是 wip/insert，包含 4 個相關函式 (可以是若干 commits，或集中一次 commit)。隨後可能會有 refactor/insert 或 refactor/size 這樣的變更，在不改變功能的前提，改進程式碼的可閱讀和可維護的程度。

仔細思考了，老師提供的分支命名方式簡潔易懂，查詢了wip簡稱的意思:
wip: work in process (個人翻譯建構中)
另外 refactor:
來源: refactor

(programming) To rewrite existing source code in order to improve its readability, reusability or structure without affecting its meaning or behaviour
重寫程式碼，在不影響其意義或行為的情況下增進可讀性、可利用性或程式結構

而且把功能相關的函式實作用一個分支名稱來代表可減少分支數量，所以到這邊我先去細看 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 分支:

$ 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:

$ git remote -v
origin	git@github.com:ihost1002/lab0-c (fetch)
origin	git@github.com:ihost1002/lab0-c (push)

發現忘記加 .git (副檔名)，下以下命令修改 url:

$ git remote set-url origin git@github.com:ihost1002/lab0-c.git

重新確認 url:

$ git remote -v
origin	git@github.com:ihost1002/lab0-c.git (fetch)
origin	git@github.com:ihost1002/lab0-c.git (push)

刪除遠端 queue_debug 分支:

$ 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 分支:

$ 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 分支:

$ 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 分支:

$ 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 分支:

$ 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 分支:

$ 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 分支:

$ 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

$ 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 教學把 queue_q_new 底下的 3 個 commit 移動到 wip/alloc。
需要基準 commit (M)， 以及要移動的 commits，命令如下:

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

$ 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:

$ 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 說到要前一個 commit，所以為 6c80a7d。過程如下:

$ 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 分支比照辦理:

$ 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:

$ 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 分支:

$ 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 都移動到新分支:

$ 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 分支，所以使用「改變分支名稱」:

$ 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分支:

$ 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:

$ 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 分支，想了想，乾脆砍掉重作好了:

$ 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:

$ 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:

$ 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 狀態:

$ 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:

$ 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:

$ 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 分支:

$ 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
wip/insert
wip/queue
wip/size

git 與 github 開發紀錄

  1. 由於 wip/queue 是由 wip/* 這些分支的 commits 組成，從後者 merge 到前者的過程中， pre-commit hook 可能會阻擋，例如不對的拼字 wip， 所以都改成 git rebase， 但是看 Git 教學系列 - rebase 之後才知道，雖然這些 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 終於知道要使用命令:
    git push origin HEAD --force
    但要先把 local 分支改成自己要的樣子，過程大致如下(以 wip/insert 為例):

$ 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 說到的，要先建立 backup 分支，如果出問題的話也不影響到原來的，經歷這件事後深有體會。
  • 也在思考如何更謹慎的寫好每一個 commit，因為一旦這個 commit 是公開且別人有參與的話，根本就不能隨便亂改。

繼續研究 Git 教學系列 - Remote and Github。

疑問

課內的疑問

對照 Dictionary.com 對 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" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。

→ 資訊科技詞彙翻譯

  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

文字訊息請避免用圖片來表示，否則不好搜尋和分類

這個找到了，原來是

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/

  1. 原始程式碼也許可以改進的部分
$ 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 宣告為:

int q_size(struct list_head *head)
{
}

這個參數是不是可以改成 const list_head *head? 因為累計 node 個數的過程不應該修改 head 或是其中任何 node 的內容，我那時候想說這樣改應該比較好所以也去改對應的 queue.h ，直到 pre-commit hook 檢查後顯示不應該去改，但改成 const list_head *head 應該是比較安全的作法

  1. pre-commit hook
/* 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 會過？

  1. 如果使用 puts、sprintf、strcpy 會有風險，那為什麼沒有人要幫忙修改裡面的實作內容讓其變為無風險呢?

  2. qtest 裡的佇列名稱仍然是 l 不是 q ，我先擱著，等其他 函式 寫完可執行之後再來找這個問題

沒有所謂的「課外」，只要讓你的專業素養變強，都算是課程的範疇。

  1. 其實有這想法是源自投影片 第 48 頁說到的，有辦法自建才真的懂，所以就想到該如何完全不借助任何 C 內建的功能，內建的 funcion 或 macro 都不使用，而是自己建立適當的 macro 或 函式，從頭到尾自建一個 printf 函式 ，我大概知道要用到 va_list, va_start, va_arg, va_end ，但我還是無法實作跟這些macro相同的功能，所以其實我不懂 ; 另外我曾經嘗試自己看 gnu 的 source code ，但是從 stdio.h 這個 header 進去研究之後，跟著 macro 定義跳來跳去，跳到最後都不知道自己看到哪了，想請問各位高手要從哪裡切入會比較有可能實際了解並實作出來? 如果方便的話歡迎提供參考的資料，我會自己先看，研究很久看不懂再請教，感謝各位！

不要說「請問各位高手..」，你應該清楚闡述，若問題能引來共鳴，自然會有人回覆你，否則你只是堆砌無助於專業討論的詞彙。

首先你該閱讀第一手材料，例如 C 語言規格書，清楚知道行為，才有辦法實作。現行的資訊教育往往造就一堆眼高手低的學員 (授課教師可能也是這樣的人，不全然是學生的錯)，後者追求用短時間給出「正確」的答案，於是初步的程式碼出現後，就沒有後續 (就像台灣媒體喜歡說「AI 元年」一類的詞彙，請問第二年和第十年在哪？)。動手！

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

感謝老師花時間批改，我會注意盡量不要用到非必要的縮排，您提到的中英文字中間要間隔大致已修改 (可能眼花漏掉)，文字訊息的圖片也都附上文字，Mark Down、Graphviz 、「Git 教學和 GitHub 設定指引」 跟 C 語言規格書 我去研究，感恩!

Last changed by 
 
ihost1002
0
352

Read more

《如果歷史是一群喵 4 東漢末年篇》

《如果歷史是一群喵 4 東漢末年篇》

May 23, 2025
2025q1 Homework1 (lab0)

contributed by &lt; ihost1002 &gt;

Mar 26, 2025
2025q1 Homework1 (ideas)

contributed by &lt; ihost1002 &gt;

Mar 9, 2025
Learn C The Hard Way學習紀錄

Exercise 17.

Nov 28, 2024
Read more from ihost1002
Published on HackMD