2025q1 Homework1 (lab0)

contributed by <miaoshahaha>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$lscpu
rchitecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   20
  On-line CPU(s) list:    0-19
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i5-14500
    CPU family:           6
    Model:                191
    Thread(s) per core:   2
    Core(s) per socket:   14
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   19%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5222.40

開發指定的佇列操作

開發準備

在實作 lab0-c 之前，要先詳閱 queue.h 以及 list.h，其中雙向鏈結串列的設計如下：

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

並且將 list_head 嵌入至結構體 element_t，可藉由 container_of 巨集推算出 list 節點的記憶體位址。

typedef struct {
    char *value;
    struct list_head list;
} element_t;

container_of 巨集可以在給定成員的型態及名稱，傳回成員的位址減去結構體的起始位址。

#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - offsetof(type, member)))

`q_new`

建立新的空佇列

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
    if (!head) {
        return NULL;
    }
    INIT_LIST_HEAD(head);
    return head;
}

先宣告一個 list_head 結構體 head，並且分配記憶體空間，如果分配空間失敗，則回傳 NULL ，這邊用到了 INIT_LIST_HEAD，可以將 head 的 next 跟 prev 指標指向自己。

這邊最一開始就要注意，當我們呼叫 malloc 的時候，並不保證每一次都會成功的分配記憶體空間，所以在呼叫 malloc 之後，必須確認是否成功分配記憶體空間，以防止 Segmentation Fault：

C99 (7.20.3)

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

`q_free`

釋放佇列所佔用的記憶體空間

void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *entry, *safe = NULL;
    list_for_each_entry_safe (entry, safe, head, list) {
        q_release_element(entry);
    }
    free(head);
}

當我們要釋放記憶體空間的時候，除了要釋放雙向環狀鏈結佇列之外，還必須
連帶將 element_t 結構體中的元素釋放，釋放的方法是遍歷佇列中每個節點，透過 list_for_each_entry 可以拜訪每個節點，而其程式碼為：

#define list_for_each_entry(entry, head, member)                   \
    for (entry = list_entry((head)->next, typeof(*entry), member); \
         &entry->member != (head);                                 \
         entry = list_entry(entry->member.next, typeof(*entry), member))

裡面的 list_entry 就是藉由 container_of 來得知其中元素所在的記憶體位址為何。

#define list_entry(node, type, member) container_of(node, type, member)

`q_insert_head`

在佇列開頭插入給定的新節點

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
        return false;
    new_ele->value = strdup(s);
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }
    list_add(&new_ele->list, head);
    return true;
}

做插入的時候先分配記憶體空間給結構體 element_t ，並且用 strdup 函式複製字串，它可以將副本的起始位址的指標回傳，最後我們透過 list_add 來新增節點至佇列開頭的下一個位置。

`q_insert_tail`

在佇列尾端插入給定的新節點

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *new_ele = malloc(sizeof(element_t));
    if (!new_ele)
        return false;
    new_ele->value = strdup(s);
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }
    list_add_tail(&new_ele->list, head);
    return true;
}

這裡的做法跟插入節點到開頭唯一的差別就是用到了 list_add_tail，
我們可以透過 list_add 以及 list_add_tail 來決定要將節點新增到頭部或尾端。

`q_remove_head`

在佇列開頭移去給定的節點

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_first_entry(head, element_t, list);
    if (sp) {
        memcpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&ele->list);
    return ele;
}

這裡的做法是要移去給定的節點，這裡有個要留意的地方是，在 queue.h 的標頭檔有說明 'remove' 和 'delete' 是不同的，我們只需要移除節點即可，而不需要釋放記憶體空間。

移去給定節點方法是，如果 *sp 不是 NULL 則將元素移除，並且將移除元素字串複製 bufsize - 1 的大小到 *sp ，然後在最後加上 NULL terminator。這裡找出字串位址的方法是透過 list_first_entry 這個巨集先找出元素的位址，再間接的找出元素中 *value 的位址。

再來有個困難的地方是如何將字串複製到 *sp ，直覺的想法是直接用 strcpy 或者是 strncpy，但我們需要的是 bufsize - 1 的大小，所以必須要給定一個複製的範圍，因此不能用 strcpy，所以想法是用 strncpy 來複製字串到 *sp 當中，不過這邊有個考量是，在 C 語言規格書中所規範的 strncpy 是：

C99 (7.21.2.4)

If the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.

如果複製字串小於我們所給定的大小，strncpy 會將超過原本字串的部分全部補 '0' ，因為是不必要的操作所以會導致效率不佳。其他的複製字串的方式就是使用 memcpy，它的差別是給定多少的大小，它就複製多少的空間，這個方法符合 q_release_head 的需求，所以我們只需要按照它的需求，複製 bufsize - 1 大小，並且在最後自行補上 NULL terminator 就可以。

`q_remove_tail`

在佇列尾端移去給定的節點

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_last_entry(head, element_t, list);
    if (sp) {
        memcpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&ele->list);
    return ele;
}

這裡的方法大致上跟 q_remove_head 相同，不一樣的地方在我們要移除的是尾端的節點，因此就用 list_last_entry 來得到尾端元素的記憶體位址，就可以做移除了。

`q_size`

計算目前佇列的總節點量

int q_size(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;

    struct list_head *next;
    int cnt = 0;

    list_for_each (next, head) {
        cnt++;
    }
    return cnt;
}

這裡只要遍歷每個節點即可，用一個計數器來計算節點數量。

`q_delete_mid`

移走佇列中間的節點

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *slow = head->next, *fast = head->next->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    element_t *del_ele = list_entry(slow, element_t, list);
    list_del(&del_ele->list);
    q_release_element(del_ele);


    return true;
}

要找出中間節點的方法只要透過快慢指標就可以快速找到，當找到中間節點之後，再透過 list_entry 得到元素的記憶體位址，接著移除節點，並釋放元素佔據的記憶體空間即可，這裡透過 queue.h 中的靜態變數 q_release_element 來釋放元素記憶體空間。

`q_swap`

void q_swap(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node, *safe;

    for (node = (head)->next, safe = node->next;
         node != (head) && safe != (head);
         node = node->next, safe = node->next) {
        list_move(node, safe);
    }
}

這邊要針對佇列中兩兩節點做交換，接著用 list_move 來交換節點。

`q_reverse`

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *node;
    struct list_head *safe;

    list_for_each_safe (node, safe, head) {
        list_move(node, head);
    }
}

以反向順序重新排列鏈結串列，並且不配置額外的記憶體空間來操作，這個做法可以透過遍歷每個節點，並且將正在拜訪的節點移到頭部，如此即可將鏈結串列反向排列。

`q_reverseK`

void q_reverseK(struct list_head *head, int k)
{
    if (!head)
        return;

    struct list_head *tmp = head;
    LIST_HEAD(tmp_head);

    struct list_head *node, *safe;
    int cnt = 0;

    list_for_each_safe (node, safe, head) {
        cnt++;
        if (cnt == k) {
            list_cut_position(&tmp_head, tmp, node);
            q_reverse(&tmp_head);
            list_splice_init(&tmp_head, tmp);
        }
        cnt = 0;
        tmp = node->next;
    }
}

透過 q_release 來進行反向順序的操作，並且使用計數器計算遍歷過的節點，當遍歷的節點等於 k ，便將該段串列進行反向排列。

在 qtest 提供新的命令 shuffle

在 qtest.c 中會呼叫 console_init() 命令，我們可以在 console_init() 中新增 shuffle 命令，觀察新增命令使用了 ADD_COMMAND 巨集如下：

#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

所以要建立新的命令，只要在 qtest.c 檔案中先提供 do_* 函式，並且在 console_init() 中新增即可，假設要新增 shuffle 命令：

bool do_shuffle(int argc, char *argv[])
{
    /* my_shuffle_function*/
    return (bool) printf("Hello, World\n");
}

2025q1 Homework1 (lab0)

開發環境

開發指定的佇列操作

開發準備

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_swap

q_reverse

q_reverseK