2024q1 Homework1 (lab0)

contributed by < LULser0204 >

Reviewed by `mervin0102`

關於 ascend 與 descend ，如果佇列的走訪方向從節點 node 走訪至 node->next 稱為正向走訪，可以將迴圈的移動從 safe = current->next; 改為 safe = current->prev; ，讓迴圈反向走訪佇列，也就是走訪方向從節點 node 走訪至 node->prev，可以省略開頭與結尾的 q_reverse ，增進函式效能。

在環狀且雙向的鏈結串列中，什麼叫做「反向」？需要明確的定義。又，「模型」是什麼？

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

在 list.h 中，函式 list_move 就包含 list_del 與 list_add ， q_swap 的實作可以考使用 list_move 使函式更為精簡。

開發環境

$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 22.04.3 LTS
Release:	22.04
Codename:	jammy

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE

$ 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):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Xeon(R) CPU E3-1231 v3 @ 3.40GHz
    CPU family:          6
    Model:               60
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            3
    CPU max MHz:         3800.0000
    CPU min MHz:         800.0000
    BogoMIPS:            6799.97

佇列實作

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

收到

在開始之前，我先觀察 list.h 檔裡面所定義的結構

雙向鏈結串列

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

以及在 queue.h 檔案第 23~26 行裡面所定義的鏈結串列元素

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

q_new

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

建立新的「空」佇列

根據老師 lab0 的教材可以得知「空」佇列的定義

「空」 (empty) 的佇列是指向有效結構，但開頭 (head) 的值為 NULL;

我使用 malloc 配置記憶體空間，若成功配置足夠空間，則讓 new 的 prev 和next 指向自身，否則返回 NULL

commit ec46a29

後來實作 q_free 時，研究在 Linux 核心中 queue 的結構，點進去 The Linux Kernel API - List Management Functions ，第一個就是 void INIT_LIST_HEAD(struct list_head *list) ，在 list.h 找到其定義後，回到 q_new 在程式碼中使用 API 實作

詳閱作業說明，自 sysprog21/lab0-c fork 再提交對應的 commits

收到，抱歉。已另外 fork 並且使用
git format-patch HEAD~20..HEAD – queue.c 將 patch 紀錄抓下來
git am /path/to/patch/files/*.patch 將修改歷史套用上去
"git pull origin master" "git push origin master"推送上去

修改後的程式碼: commit 9e38721

q_free

commit 3eee3a5

使用你 fork 後得到的 GitHub repository 對應的超連結，也就是以 https://github.com/LULser0204/lab0-c 開頭

已修改

釋放佇列所佔用的記憶體

文字訊息不要用圖片展現，而且上傳圖片要留意權限。

收到

實作:

在你所不知道的 C 語言: linked list 和非連續記憶體觀察佇列在 Linux 核心中的結構，先用 list_for_each_safe 走訪所有成員，而 node 紀錄該成員的位址，釋放該節點所指向的 value ，接著使用 list_del函式移去該節點，再釋放 element_t 。

最後也需要將 head 的 list_head 記憶體也釋放。

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

收到

insert_head

commit 8575d8a

在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)

先檢查佇列是否為空，為空則 return false

接著先配置記憶體給新節點 new_head ，接著再配字記憶體給字串，如果配置成功，則用 strcpy 將內容複製到 new_head 。
最後在使用 list_add 將指定的節點插入佇列 head 的開頭

但我在 git 上去的時候，跳出這訊息

Following files need to be cleaned up:
queue.c
Dangerous function detected in /home/vision/linux2024/lab0-c/queue.c
56:    strcpy(new_head->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.
    https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

Common vulnerabilities guide for C programmers 提到:

strcpy
The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp.

所以我做了以下變更，使用了 strncpy 來避免 buffer overflow ，並手動增加 '\0' 字元以符合佇列的規範

詳閱作業說明，自 sysprog21/lab0-c fork 再提交對應的 commits

insert_tail

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

收到

在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)

概念上和 insert_head 相同，唯一不同的地方在於使用 list_add_tail 來將指定的節點插入 head 的尾端。

commit f151ea7

remove_head

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

在佇列開頭 (head) 移去 (remove) 給定的節點

由於是雙向鏈結串列，所以 head->next 為佇列的第一個元素，只需要使用 list_del 移除第一個元素，之後透過 list_entry 將 list_head 的 entry 回傳即可。

但再我測試 trace-08-robust 顯示以下內容:

cmd>new
l = []
cmd> rh
Warning: Calling remove head on empty queue
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

但當我執行 remove_tail 時，卻沒這問題，所以我更改了判斷邏輯讓函式更明確的檢查鏈節列表是否為空。

commit ee38aaa
commit 6f13172
後來使用了 list_first_entry 簡化了函式
commit 9a3c355

remove_tail

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

在佇列尾端 (tail) 移去 (remove) 給定的節點，概念上和 remove_head 相似。

由於是雙向鏈結串列，所以 head->prev 為佇列的最後一個元素。只需要使用 list_del 移除第一個元素，之後透過 list_entry 將 list_head 的 entry 回傳即可。

詳細實作: commit ee38aaa

後來使用了 list_last_entry 簡化了函式
commit 9a3c355

delete_mid

commit e488d2a

修正上方超連結，對應到實際修改的 commit，而非 patch!

抱歉，已重用

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

已修改

移走佇列中間的節點。

參考你所不知道的 C 語言: linked list 和非連續記憶體使用快慢指標來找出佇列的中點，迴圈結束後 slow 指向的正是中間節點，接著使用 list_del 刪除並釋放記憶點空間

注意用語

收到

原理: fast 指標每次移動兩個，而 slow 指標只移動一格，故結束後慢指標位置就會在中點

考慮到環狀且雙向鏈結串列，你能否撰寫更快更精簡的程式碼？

能。因為是環狀的關係，所以可以讓兩個指標從不同方向前進。
現在有個環狀的串列有 9 個節點。假設 fast 指標逆時針移動， slow 指標順時針移動，則只需 3 輪便可找到中點；如果兩個指標都順時針移動的話，則需要 4 輪。

delete_dup

在佇列已經排序的狀況下，移走佇列中具備重複內容的節點。

使用 list_for_each_entry_safe 走訪每個節點，並且分別用 before 和 tmp 紀錄當前節點和下個節點是否相同

flag 來記錄當前節點是不是重複

用 tmp 來承擔被刪除與釋放空間的任務。我當時想說刪除 before (畢竟 tmp 記錄下一個節點的位置了)不會怎樣，結果一直觸發 "Segmentation fault" 問 chatgpt 才知道是什麼問題

但當我覺得這麼改會沒問題的時候， "Segmentation fault" 還是一直發生， chatgpt 告訴我釋放 tmp 後，嘗試存取它，可能會導致未定義行為，後來改用 q_release_elememt 來釋放節點。

access 的翻譯是「存取」，而非「訪問」(visit)

已修正

使用 q_release_element 確保正確釋放，並再釋放後不再存取它

詳細實作:commit 536d842
修改好的實作:commit 95c742b

q_swap

交換佇列中鄰近的節點

交換兩個相鄰節點的位置 (in pairs)。直覺上想到的方法是先用 nextnext 紀錄下一輪的位置，再用 cur 和 tmp 分別記錄該輪數組 (兩兩一組)第一個元素及第二個元素，使用 list_add 和 list_del 完成交換位置

commit 3a7f681

q_reverse

commit 7d7ee93

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點

經過 q_swap 的實作經驗後，反轉鏈結串列只需要用 list_for_each_safe 走訪每個結點，並將每個節點用 list_del 和 list_add 讓各個節點從頭加入佇列，就能達到反轉的效果

q_reverseK

commit e976c76

類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列

我直覺上的想法是用兩層迴圈，第一次跑的次數是有「幾組」節點用 q_size(head)/k，第二層則跑 k 次。
在最裡面那層迴圈的作法和將整個 q_reverse 相似，將這輪翻轉的子佇列先接在另一條佇列上，最後再將其用 list_splice 接回 head

q_sort

commit 491cd41

digraph G {
    node [shape=record, height=.1];
    
    subgraph cluster_0 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a0 [label="2 | 5 | 4 | 6"];
        a1 [label="8 | 1 | 7 | 3"];
        label = "unsorted list";
        color=cyan2;
    }

    subgraph cluster_1 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a2 [label="2 | 5"];
        a3 [label="4 | 6"];
        a4 [label="8 | 1"];
        a5 [label="7 | 3"];
        label = "divide";
        color=cyan2;
    }

    subgraph cluster_2 {
        style=filled;
        color=lightgrey;
        node [style=filled, color=white];
        a6 [label="2"];
        a7 [label="5"];
        a8 [label="4"];
        a9 [label="6"];
        a10 [label="8"];
        a11 [label="1"];
        a12 [label="7"];
        a13 [label="3"];
        label = "sorted lists";
        color=coral;
    }

    subgraph cluster_3 {
        style=filled;
        node [style=filled];
        b0 [label="2 | 5"];
        b1 [label="4 | 6"];
        b2 [label="1 | 8"];
        b3 [label="3 | 7"];
        label = "merge";
        color=darkolivegreen1;
    }

    subgraph cluster_4 {
        style=filled;
        node [style=filled];
        c0 [label="2 | 4 | 5 | 6"];
        c1 [label="1 | 3 | 7 | 8"];
        label = "merge";
        color=darkolivegreen1;
    }

    subgraph cluster_5 {
        style=filled;
        node [style=filled];
        d [label="1 | 2 | 3 | 4 | 5 | 6 | 7 | 8"];
        label = "final merge";
        color=darkolivegreen1;
    }
    a0 -> a2;
    a0 -> a3;
    a1 -> a4;
    a1 -> a5;
    
    a2 -> a6;
    a2 -> a7;
    a3 -> a8;
    a3 -> a9;
    a4 -> a10;
    a4 -> a11;
    a5 -> a12;
    a5 -> a13;
    
    a6 -> b0;
    a7 -> b0;
    a8 -> b1;
    a9 -> b1;
    a10 -> b2;
    a11 -> b2;
    a12 -> b3;
    a13 -> b3;

    b0 -> c0;
    b1 -> c0;
    b2 -> c1;
    b3 -> c1;

    c0 -> d;
    c1 -> d;
}

以遞增順序來排序鏈結串列的節點，可參閱 Linked List Sort 得知實作手法

參考你所不知道的 C 語言: linked list 和非連續記憶體提到的方法

將整個數列不停地拆成兩推，直到每堆只剩下一個元素，再兩兩合併直到合併成一個數列為止。我一開始想法是用前面使用前面的 delete_mid ，來將佇列分成兩段閉循環的佇列，但會一直觸發 Segmentation fault occurred

後來，參考 wanghanchi 學長採取將環狀鏈結串列斷開，子串列的結尾設為 NULL ，當成單向鏈結串列處理，如此一來也能在迭代的時候方便判斷是否抵達尾端。

split 函式:使用前面提到的快慢指針找到中點，再將其拆成兩半；

mergeSort 函式: left 和 right 逐一比較，但我那時候沒有考慮到一種情形：如果 left 都用完， right 還有兩個以上的情形，所以我測試的時候總是會有幾個元素消失

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

當 mergeSort 函式內迴圈結束時，代表著 left 或 right 其中一個已為空。所以增加一個判斷式看哪條串列為空，沒空的串列接在合併的串列後面。藉由此判斷式，可以涵蓋演算法最差狀況。

through 不該寫作「通過」，否則你如何區分 pass 的翻譯？
回去看 qtest 目前的隨機資料輸入，如何產生合併排序演算法會遇到的最差狀況的測試資料？

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

我跑去看了 qtest 的隨機資料輸入，使用這一段生成

static void fill_rand_string(char *buf, size_t buf_size)
{
    size_t len = 0;
    while (len < MIN_RANDSTR_LEN)
        len = rand() % buf_size;

    randombytes((uint8_t *) buf, len);
    for (size_t n = 0; n < len; n++)
        buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
    buf[len] = '\0';
}

參考 stackoverflow 這篇文章，合併排序演算法會遇到的最差狀況是 "需要進行最多比較的時候" ，也就是每對集合中都參與比較。
所以如果要產生最差狀況的測試資料，可以使用 q_sort 生成降序的字串。

q_sort :把環狀結構斷開，以及最後將整個串列的環狀結構接回來

函式 q_sort 不完整，請整合 q_sort 與 mergesort

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 →

marvin0102

q_ascend

commit 01bfcbf

參閱 LeetCode 2487. Remove Nodes From Linked List，在佇列中該「位置」的右邊不能有大於他的數字存在

正確使用標點符號。

我的想法是先用 q_reverse 翻轉整個佇列，接著從左往右走訪每個節點。假設一個變數 max 初始值為該佇列的第一個值，往右走訪的路上會有兩個情形:

1.如果碰到該節點的值比 max 還要小，則移去掉它
2.如果碰到該節點的值比 max 還要大，則更新 max 的值為該節點的值繼續走訪直到最後一個節點

最後，再將整個佇列翻轉回來並用 q_size 傳回佇列的長度

如果調整刪去的條件，是否可以省略 q_reverse 的呼叫?

可以，除了調整刪去的條件以外，也能從右往左(因為是環狀且雙向)
commit 5c4cfdb

謝謝哥，我懂你的意思了
commit fc05e7a

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 →

marvin010

q_descend

commit 7d3a25e

參閱 LeetCode 2487. Remove Nodes From Linked List，在佇列中該 "位置" 的右邊不能有小於他的數字存在

其作法和 ascend 概念相同，只是從找是否有"更大"的值變成找"更小"的值。

既然 q_decend、q_ascend 概念相同，能否將兩函式整合，使程式更簡潔?

可以，如果 ascend 可以多帶進去一個參數( bool ascend )，判斷遞增還是遞減的排序，這樣就只需要在刪去條件那調整即可。

或者是用 q_reverse 翻轉串列，呼叫 q_ascend 然後再用 q_reverse 翻轉回來
commit fc05e7a

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 →

marvin0102

q_merge

commit 15f08f4

合併所有已排序的佇列，並合而為一個新的已排序佇列，詳見 LeetCode 23. Merge k Sorted Lists

我一開始認為傳進來的會是多條佇列，所以我嘗試使用 q_sort 所使用到的 mergesort 函式，將其兩兩合併成一條，但失敗了。後來，參考 ItisCaleb 的作法，發現有 queue_contex_t 的存在，直接將 queue_contex_t google 搜尋會跳出 SPFishcool 所整理的架構圖!

無效的超連結，檢查權限設定

改用 imgur 上傳，避免權限設定

引用 SPFishcool 的內文。queue_contex_t 在紀錄每一條佇列的資訊，*q 為 pointer of queue head，size 是佇列裡面 element_t 的數量，chain 為與其他 queue_contex_t 串連的 list_head，下面是其內容

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

在了解架構後，把每個 list 都接到第一個 list 後面，並且累加元素數量，然後再使用 q_sort 去排序

為甚麼不直接將 queue_contex_t 中的陣列直接做 merge?
先將陣列連接起來再呼叫 q_sort ，在排序時又會經過拆分與合併，顯然有點多此一舉。

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 →

marvin0102

實測結果:

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
ERROR: Probably not constant time or wrong implementation
Probably constant time
Probably constant time
---     trace-17-complexity     0/5
---	TOTAL		95/100

~~測試結果不穩定~~ 。原因是 ascend 和 descend 有時候會誤刪節點，有時候則正常運作。

後來注意到是因為刪去條件原本是 strcmp(max,tmp->value) > 0 ，但這樣會刪掉重複的節點&第一個節點，改成 >= 即可。

查閱辭典，理解「穩定」的寓意，用字該精準

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

很奇怪，我的 ascend 只有呼叫 descend 而已，結果功能是正常的???
我嘗試了很久，還是不知道為什麼這樣結果是對的。原本的想法是先把串列最後一個節點暫時移除，翻轉第 1~n-1 再接上移除的節點，之後呼叫 descend ，處理後的串列在重複前面的操作。

我搞錯了 ascend 的定義…以及輸入 [5,2,13,3,8] 之所以只輸出 [8]
是因為我前面都用 char ，所以 '13' 他比較的對象是字元 '1' 而不是數字 13

linked list 為「鏈結串列」，可簡稱為 list (串列)，但不可稱「链表」，該資料結構不具備任何「表」的寓意，參見中華民國教育部重編國語辭典「表」，指「分格或分項以列記事物的文件」，而 linked list 作為資料結構，全然沒有「分格」和「分項」的意涵。

\(\to\) 資訊科技詞彙翻譯

不小心把 ChatGPT 的文字寫上去= =

從我的實作可以看到我的作法屬於是 bad taste 那種只考慮能不能動…，還需要磨練能力把學到的東西拿出來使用。
太過於依賴 Chatgpt 或是網路論壇上的解答

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

2024q1 Homework1 (lab0)

Reviewed by `mervin0102`

開發環境

佇列實作

q_new

q_free

實作:

insert_head

insert_tail

remove_head

remove_tail

delete_mid

delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_descend

q_merge

實測結果:

以 Valgrind 分析記憶體問題

整合 tiny-web-server

在 qtest 提供新的命令 shuffle

研讀 Linux 核心原始程式碼的 lib/list_sort.c

改進 dudect 實作

2024q1 Homework1 (lab0)

Reviewed by mervin0102

開發環境

佇列實作

q_new

q_free

實作:

insert_head

insert_tail

remove_head

remove_tail

delete_mid

delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_descend

q_merge

實測結果:

以 Valgrind 分析記憶體問題

整合 tiny-web-server

在 qtest 提供新的命令 shuffle

研讀 Linux 核心原始程式碼的 lib/list_sort.c

改進 dudect 實作

Reviewed by `mervin0102`