# Linux 核心專題: 重作第一次作業
> 執行人: YeeeLiang
> [專題解說影片](https://youtu.be/eoU7hsAPRQ4)
### 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 (間接指標) 的時候，實際上是通過指向指向節點的指標來進行操作。這樣做的好處是，我們可以直接存取到我們想要修改的指標，而不需要逐一走訪每個節點。尤其是當操作的節點數量非常大時，這樣做可以提高效率。
如上圖，如果我們想要刪除節點 3，我們可以使用 indirect pointer。將 indirect pointer 指向指向節點 3 的指標。通過這種方式，直接存取並修改指向節點 3 的指標，從而刪除節點 3，而無需逐一走訪每個節點。因此，時間的複雜度為 O(1)。
總的來說，使用 indirect pointer 可以提高在鏈結串列中進行刪除操作的效率，特別是當我們需要頻繁地刪除節點時。
實作程式碼如下，原有三個節點存在，利用 indirect pointer 的方法將第二個節點刪除。
:::danger
注意書寫規範：
* 使用 lab0 規範的程式碼書寫風格，務必用 clang-format 確認一致
:::
:::info
已修正，感謝提醒。
```diff
- void remove_list_node(List *list, Node *target)
- {
Node **indirect = &list->head;
```
```diff
+ void remove_list_node(List *list, Node *target) {
Node **indirect = &list->head;
```
:::
```c
#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 及運行程式碼。
```c
~$ ./a.out
```
可得到下面的結果：
```c
Original list: 1 2 3
List after removal: 1 3
```
## TODO: 重作第一次作業
我選擇了 `25077667` 以及 `vax-r` 這兩位同學的 lab0 實作筆記作為參考，在[`25077667`同學的筆記](https://hackmd.io/@25077667/SkpLspWnT)加入了很多創新的想法並改寫了原本作業給的程式碼；而[`vax-r`同學的筆記](https://hackmd.io/@vax-r/linux2024-homework1)則是整理的相當清晰易懂。
[lab0 的作業](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)要求是實作 a chain of circular queues，這並非是單純一個 queue，而是被鏈結串列所串連在一起的多個環狀佇列。如圖：
### `q_new()`
使用 `calloc` 函式來分配記憶體，確保新的佇列 head 節點 `new_qhead` 被初始化為零，並分配足夠大小以容納 `struct list_head` 的資料。當分配失敗時（`new_qhead` 為 NULL），函式返回 NULL，無法創建新的佇列。假若一切順利，函式則返回指向新佇列 head 節點的指標。
```c
/* 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。
```c
/* 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 數量。
```c
/* 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` 相遇或者相鄰。
```c
/* 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;`。
```c
/* 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，則跳出迴圈，避免處理最後一對可能是**奇數**個節點的情況。
```c
/* 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` 鏈節串列以便下一次使用。
```c
/* 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);
}
```
Sign in with Wallet
Connect another wallet