Linux 核心專題: 重作第一次作業

執行人: YeeeLiang
專題解說影片

Review by 'Ken-LuWeiRu'

在'lab0 的作業要求是實作 a chain of circular queues，這並非是單純一個 queue，而是被鏈結串列所串連在一起的多個環狀佇列。如圖：' 此圖已經是用 graphviz 製作而成，可以直接在 hackmd 中使用 graphviz 的程式碼呈現作圖，用法如下

```graphviz
放置 graphviz 程式碼
/```

任務簡介

解釋 remove_list_node 的 indirect pointer 運作原理
重作第一次作業，彙整其他學員的成果 (挑出優秀的學員成果、重現實驗、檢驗出處 [數學推導]，並修正錯誤)，著重在程式開發的技巧 (e.g., indirect pointer, git commit message 的撰寫, 排序演算法的調整, 排序的 stability)。

TODO: 解釋 remove_list_node 的 indirect pointer 運作原理

搭配案例來說明

"Indirect pointer" 意味著使用指向指標的指標，這使得能夠修改指標所指向的內容，而不是僅僅修改指標本身。

remove_list_node 函式用於從鏈結串列中刪除節點。當我們使用 indirect pointer (間接指標) 的時候，實際上是通過指向指向節點的指標來進行操作。這樣做的好處是，我們可以直接存取到我們想要修改的指標，而不需要逐一走訪每個節點。尤其是當操作的節點數量非常大時，這樣做可以提高效率。

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 →

如上圖，如果我們想要刪除節點 3，我們可以使用 indirect pointer。將 indirect pointer 指向指向節點 3 的指標。通過這種方式，直接存取並修改指向節點 3 的指標，從而刪除節點 3，而無需逐一走訪每個節點。因此，時間的複雜度為 O(1)。

總的來說，使用 indirect pointer 可以提高在鏈結串列中進行刪除操作的效率，特別是當我們需要頻繁地刪除節點時。

實作程式碼如下，原有三個節點存在，利用 indirect pointer 的方法將第二個節點刪除。

注意書寫規範：

使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致

已修正，感謝提醒。

- void remove_list_node(List *list, Node *target)
- {
      Node **indirect = &list->head;

+ void remove_list_node(List *list, Node *target) {
      Node **indirect = &list->head;

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct List {
    Node *head;
} List;

void remove_list_node(List *list, Node *target) {
    Node **indirect = &list->head;
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
    free(target);
}

void print_list(List *list) {
    Node *current = list->head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

int main() {
    List list;
    list.head = (Node *)malloc(sizeof(Node));
    list.head->data = 1;
    list.head->next = (Node *)malloc(sizeof(Node));
    list.head->next->data = 2;
    list.head->next->next = (Node *)malloc(sizeof(Node));
    list.head->next->next->data = 3;
    list.head->next->next->next = NULL;

    printf("Original list: ");
    print_list(&list);

    remove_list_node(&list, list.head->next);

    printf("List after removal: ");
    print_list(&list);

    Node *current = list.head;
    while (current != NULL) {
        Node *temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

這段程式碼在一開始定義了兩個結構，Node 表示鏈結串列中的節點，包含一個整數和指向下一個節點的指標；List 表示整個鏈結串列，包含一個指向鏈結串列 Head 的指標。

然後，用 remove_list_node 函式從鏈結串列中移除指定的節點。該函式接受兩個參數，一個是指向鏈結串列的指標，另一個是要被移除的節點的指標。在函式內部，我們使用了一個間接指標 indirect，這個指標指向將要更新的地方。然後，逐一走訪鏈結串列，直到找到指向要刪除節點的指標，然後更新這個指標，跳過該節點，並釋放其佔用的記憶體。

最後，使用 GDB 進行 debug 及運行程式碼。

~$ ./a.out

可得到下面的結果：

Original list: 1 2 3
List after removal: 1 3

TODO: 重作第一次作業

我選擇了 25077667 以及 vax-r 這兩位同學的 lab0 實作筆記作為參考，在25077667同學的筆記加入了很多創新的想法並改寫了原本作業給的程式碼；而vax-r同學的筆記則是整理的相當清晰易懂。

lab0 的作業要求是實作 a chain of circular queues，這並非是單純一個 queue，而是被鏈結串列所串連在一起的多個環狀佇列。如圖：

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 →

`q_new()`

使用 calloc 函式來分配記憶體，確保新的佇列 head 節點 new_qhead 被初始化為零，並分配足夠大小以容納 struct list_head 的資料。當分配失敗時（new_qhead 為 NULL），函式返回 NULL，無法創建新的佇列。假若一切順利，函式則返回指向新佇列 head 節點的指標。

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new_qhead = calloc(1, sizeof(struct list_head));
    if (!new_qhead)
        return NULL;
    INIT_LIST_HEAD(new_qhead);
    return new_qhead;*
}

進一步探討 malloc 與 calloc 的差異為何？malloc 函式（memory allocation）用於分配指定大小的記憶體區塊，並返回一個指向該記憶體區塊起始位置的指標。但malloc分配的記憶體中的內容是未初始化的，意旨它們的值可能是隨機的或者舊的內容。而calloc 函式（contiguous allocation）將分配的每一位元組初始化為零。因此可預知malloc 的效能比 calloc 快，因為 calloc 需要額外的時間來初始化記憶體，但內容相對的不安全。

`q_insert_head()`

這個函式的目的是將一個新的 element 插入到佇列的 head。在這裡使用了Linux核心的連結串列結構 struct list_head *head，將 head 指向佇列的 head。

/* Insert an element at head of queue */
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;
    INIT_LIST_HEAD(&new_ele->list);
    new_ele->value = strdup(s);
    if (!new_ele->value) {
        free(new_ele);
        return false;
    }
    list_add_tail(&new_ele->list, head);
    return true;
}

`q_size()`

計算佇列中 element 數量的函式。使用 list_for_each 逐一走訪佇列。每走完一次，就將 size 變數加一，以計算佇列中的element 數量。

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int size = 0;
    struct list_head *cur;
    list_for_each (cur, head)
        size++;
    return size;
}

`q_delete_mid()`

刪除佇列中中間的節點。使用 struct list_head *head 指向佇列的 head 節點的指標。使用兩個指標 first 和 second 來尋找中間節點。通過從佇列的兩端同時向中間移動，直到 first 和 second 相遇或者相鄰。

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || list_empty(head))
        return false;

    struct list_head *first = head->next;
    struct list_head *second = head->prev;
    while((first != second) && (first->next != second)) {
        first = first->next;
        second = second->prev;
    }
    element_t *node = list_entry(first, element_t, list);
    list_del(first);
    free(node->value);
    free(node);
    return true;
}

`q_delete_dup()`

刪除佇列中所有具有重複字串的節點。以下程式碼主要運用了雙重循環來處理重複節點的刪除操作，並且在操作過程中釋放了相關的記憶體。

在循環中，首先檢查是否存在重複節點。條件 &tmp->list != head && !strcmp(cur->value, tmp->value) 確保 tmp 不是頭節點並且 cur 和 tmp 的值相同。
如果有重複，則刪除 cur 節點，並釋放其記憶體。設置 dup = true; 表示有重複節點被處理。
如果前一個節點已經有重複節點被刪除（即 dup == true），則直接刪除 cur 節點，並重置 dup = false;。

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    bool dup = false;
    element_t *cur, *tmp;
    list_for_each_entry_safe (cur, tmp, head, list) {
        if (&tmp->list != head && !strcmp(cur->value, tmp->value)) {
            list_del(&cur->list);
            free(cur->value);
            free(cur);
            dup = true;
        } else if (dup) {
            list_del(&cur->list);
            free(cur->value);
            free(cur);
            dup = false;
        }
    }
    return true;
}

`q_swap()`

透過雙向鏈節串列（doubly-linked list）的資料結構來實作交換每兩個相鄰節點的功能。在每次迴圈中，first 和 second 分別指向相鄰的兩個節點。如果 second 指向的是 head，則跳出迴圈，避免處理最後一對可能是奇數個節點的情況。

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *first, *second;
    list_for_each_safe (first, second, head) {
    if (second == head)
        break;
        first->prev->next = second;
        second->prev = first->prev;
        first->next = second->next;
        first->prev = second;
        second->next->prev = first;
        second->next = first;
    }
}

`q_reverseK()`

將鏈節串列每 k 個節點進行一次反轉。這裡使用了 q_size 函式來計算鏈節串列的節點總數，然後將其除以 k，得到需要進行反轉的次數 times，每次反轉都處理 k 個節點。

tail 是一個指向 struct list_head 的指標，用於在每個迭代中找到反轉的結束點。tmp 是一個新的空鏈節串列，用來暫時存放反轉後的 k 個節點。

new_head 是最終結果的新鏈節串列的頭。使用 list_for_each 來逐一走訪鏈節串列，直到找到第 k 個節點（即 tail），或者是逐一走訪完整個鏈節串列。確保 tail 指向每次反轉的結束位置。

接著使用 list_cut_position 將從 head 到 tail->prev 的節點切下來，並將它們放入 tmp 鏈節串列中。然後使用 q_reverse 函式來反轉 tmp 鏈節串列中的節點。

最後使用 list_splice_tail_init 將 tmp 鏈節串列中的節點接入 new_head 鏈節串列的尾部，並且初始化 tmp 鏈節串列以便下一次使用。

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    if (!head)
        return;

    int times = q_size(head) / k;
    struct list_head *tail;

    LIST_HEAD(tmp);
    LIST_HEAD(new_head);

    for (int i=0; i < times; i++) {
        int j = 0;
        list_for_each(tail, head) {
            if (j >= k)
                break;
            j++;
        }
        list_cut_position(&tmp, head, tail->prev);
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, &new_head);
    }
    list_splice_init(&new_head, head);
}