2023q1 Homework1 (lab0)
contributed by < WangHanChi >
作業要求
- 完成實作 queue.c 所有功能
make test取得 100 分- 研讀
lib/list_sort.c並將其加入專案中 - 實作新的命令
shuffle - 完成 entropy 相關命令 / 選項
- 研讀論文〈Dude, is my code constant time?〉並且解釋 Student’s t-distribution 及程式實作的原理
- 使用 Valgrind 排除 qtest 實作的記憶體錯誤
- 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
- 實作
selectsystem call 來完成 lab0-c 中的 web 功能
開發環境
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
$ lscpu | less
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 5600X 6-Core Processor
CPU family: 25
Model: 33
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU max MHz: 4650.2920
CPU min MHz: 2200.0000
BogoMIPS: 7385.75
開發紀錄
以鏈結串列實作佇列
- q_new
- q_free
- q_insert_head
- q_insert_tail
- q_remove_head
- q_release_element
- q_size
- q_delete_mid
- q_delete_dup
- q_swap
- q_reverse
- q_reverseK
- q_sort
- q_merge
- q_descend
開發過程
常用結構 struct
Linked list_head
struct list_head {
struct list_head *prev;
struct list_head *next;
};
queue element_t
typedef struct {
char *value;
struct list_head list;
} element_t;
queue_contex_t
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
常用巨集
INIT_LIST_HEAD
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
將 head 往前指標與往後指標都指向自己, 並且這個 head 不會有資料
list_entry
#define list_entry(node, type, member) container_of(node, type, member)
這個巨集主要是藉由 list 取得每個 member 的起始位置, 與 container_of 功能一致
會定義成 list_entry 是為了符合 list 的風格，關於 Container_of 可以參考你所不知道的 C 語言: linked list 和非連續記憶體
digraph container {
rankdir=LR;
node[shape=record];
compound=true;
style=bold;
subgraph cluster_0 {
container [label = "container" style=filled,color=white];
subgraph cluster_1 {
node [shape=record];
element [label="|{|}", style="bold"];
label = "member"
}
}
element -> container[ltail=cluster_1, lhead=cluster_0];
}
list_for_each_entry_safe
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
#undef __LIST_HAVE_TYPEOF
這個主要是 list_for_each_safe 與 list_for_each_entry 兩個巨集的功能整合
Entry代表可以取用到member成員的資料safe代表它會紀錄下一個node來方便使用者刪除目前的node
queue 功能實作
q_new
根據要求，將回傳一個空的 list_head ，可以從 list.h 找到 INIT_LIST_HEAD 這個函式，並且會把 next 與 prev 都指向 head
- 實作流程
- 使用
malloc分配一個記憶體空間，如果分配失敗就回傳NULL - 使用
INIT_LIST_HEAD對剛剛的list_head進行初始化 - 回傳初使化的
list_head
- 使用
完整程式碼
struct list_head *q_new()
{
struct list_head *empty = malloc(sizeof(struct list_head));
if (!empty)
return NULL;
INIT_LIST_HEAD(empty);
return empty;
}
q_free
根據要求，需要把所有 queue 所配置的記憶體釋放掉，也因為會需要走訪整個 queue 且又需要釋放記憶體空間，會使用前面提及的巨集 list_for_each_entry_safe 來精簡程式碼
會使用到釋放 queue 節點的函式
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
- 實作流程
- 檢查
list_head是否為空，若為空就離開函式 - 宣告用來走訪
list的迭代器, 當前queue節點以及當前queue節點的下一個 - 使用
list_for_each_entry_safe進行走訪，在每個節點都先釋放list_head，接著再使用q_release_element這個函式來釋放這個queue中的資料與自己 - 釋放
list_head的head
- 檢查
完整程式碼
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *iter = l;
element_t *node, *node_safe;
list_for_each_entry_safe (node, node_safe, iter, list) {
list_del(&node->list);
q_release_element(node);
}
free(l);
}
q_insert_head
根據引數，會得到鏈結串列的 head 以及字串 s，需要新建一個 queue 的節點，並且將字串拷貝給節點的 value。 
字串需要以 \0 作為結尾
- 實作流程
- 檢查
list_head是否為空，若為空就回傳NULL - 為新增的
queue節點配置記憶體空間，並且檢查是否配置成功 - 配置字串
str所需要的大小，並且檢查是否配置成功 - 複製字串
s給str，並且把結尾設置為\0 - 使用
list.h中的函式list_add將這個新的節點插入到鏈結串列的head，完成後就回傳true
- 檢查
原本沒有做好的部份
- 在進行commit 的時候被 cppcheck 檢查出有記憶體未被釋放，於是開始檢查這個函式，發現在成功配置
queue的節點後，如果字串str的配置失敗的情況下，要記得釋放節點queue再離開函式 - 原本程式碼呼叫三次
strlen(s)，經過老師的提醒後，修改成使用一個變數儲存這個字串的大小因為
strlen(s)的時間複雜度為 \(O(n)\) 如果大量使用且字串長度變長的話，會降低效能
完整程式碼
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
int str_size = (strlen(s) + 1) * sizeof(char);
node->value = malloc(str_size);
if (!node->value) {
free(node);
return false;
}
memcpy(node->value, s, str_size - 1);
node->value[str_size - 1] = '\0';
list_add(&node->list, head);
return true;
}
q_insert_tail
此部份與 q_insert_head 的實作方法大同小異，僅需要將 list_add 的插入點從原本鏈結串列的頭改成尾端即可，需要注意的地方也相同
- 實作流程
- 檢查
list_head是否為空，若為空就回傳NULL - 為新增的
queue節點配置記憶體空間，並且檢查是否配置成功 - 配置字串
str所需要的大小，並且檢查是否配置成功 - 複製字串
s給str，並且把結尾設置為\0 - 使用
list.h中的函式list_add將這個新的節點插入到鏈結串列的tail，完成後就回傳true
- 檢查
完整程式碼
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
if (!node)
return false;
int str_size = (strlen(s) + 1) * sizeof(char);
node->value = malloc(str_size);
if (!node->value) {
free(node);
return false;
}
memcpy(node->value, s, str_size - 1);
node->value[str_size - 1] = '\0';
list_add_tail(&node->list, head);
return true;
}
q_remove_head
根據要求，此函式會將 queue 的 head 節點移除，並且根據 bufsize 把原本節點的資料存進 *sp 這個字串中。可以從Difference between “delete” and “remove”中得知 delete 與 remove 這兩個的不同
- 實作流程
- 檢查
head是否為NULL以及透過list_empty這個函式檢查鏈結串列是否為空的 - 使用
list_entry取得要移除的節點 - 檢查 bufsize 是否為0，之後再進行字串的拷貝
- 使用
list.h中提供的list_del將這個節點移除並且把他的前後兩個節點相連 - 回傳指向我們所移除節點的指標
- 檢查
完整程式碼
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove_node = list_entry(head->next, element_t, list);
if (bufsize) {
strncpy(sp, remove_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&remove_node->list);
return remove_node;
}
q_remove_tail
此部份與 q_remove_head 的實作方法大同小異，僅需要將 list_del 的移除點從原本鏈結串列的開頭改成尾端即可，也就是在 list_entry 的 ptr 部份把 head->next 改成 head->prev，其他需要注意的地方也相同
- 實作流程
- 檢查
head是否為NULL以及透過list_empty這個函式檢查鏈結串列是否為空的 - 使用
list_entry取得要移除的節點 - 檢查 bufsize 是否為0，之後再進行字串的拷貝
- 使用
list.h中提供的list_del將這個節點移除並且把他的前後兩個節點相連 - 回傳指向我們所移除節點的指標
- 檢查
TODO
在聽過老師的 Code Review 後，學到了一種更簡潔且程式碼共用行高的寫法
完整程式碼
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *remove_node = list_entry(head->prev, element_t, list);
if (bufsize) {
strncpy(sp, remove_node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&remove_node->list);
return remove_node;
}
q_size
根據要求，可以使用 list_for_each 這個走訪的函式來進行實作
- 實作流程
- 檢查
head是否為NULL以及透過list_empty這個函式檢查鏈結串列是否為空的 - 走訪節點並且每經過一個節點就將計數器＋１
- 回傳計數器的值
- 檢查
完整程式碼
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int count = 0;
list_for_each (head->next, head) {
++count;
}
return count;
}
q_delete_mid
Leetcode
struct ListNode* deleteMiddle(struct ListNode* head){
if(!head || head->next == NULL)
return NULL;
struct ListNode *rabbit = head, *turtle = head;
while(!(rabbit->next == NULL) && !(rabbit->next->next == NULL)){
rabbit = rabbit->next->next;
if(rabbit == NULL || rabbit->next == NULL)
break;
turtle = turtle->next;
}
turtle->next = turtle->next->next;
return head;
}
根據要求，將鏈結串列中點刪除。在 2095. Delete the Middle Node of a Linked List 上我所採用的方式為d快慢指標的方式，設定一個指標 rabbit 一次移動2個 node，另一個指標 turtle 一次移動1個 node 。當 rabbit 移動到結尾的時候， turtle 的下一個 node 便是中點。於是我將這樣的思路搬到 q_delete_mid 上
- 實作流程
- 檢查
head是否為NULL以及透過list_empty這個函式檢查鏈結串列是否為空的 - 將
rabbit與turtlr的起點都設定在head - 使用 do-while 迴圈
- do : 先將
rabbit移動兩個 node 後，檢查是否到達鏈結串列的尾端或是回到head，若尚未到達就將turtle移動一個 node - while : 檢查
rabbit檢查是否到達鏈結串列的尾端或是回到head
- do : 先將
- 將
turtle的下一個 node 使用list_entry取得佇列的元素，再將其刪除
- 檢查
發現可以改進的地方
原本使用的快慢指標適用於環狀與非環狀的 Linekd list，並且他的時間複雜度為 \(O(\frac{n}{2})\) 可以近似於 \(O(n)\) ，但是他的缺點是 rabbit 指標每次移動時會需要讀取兩次 next ，而 turtle 則需要讀取一次 next ，加總來看，每次移動需要花費三個記憶體操作的時間。
但是在環狀的 Linked-list 有一種方法也可以在相同的時間複雜度完成要求並且記憶體操作為快慢指標的 \(\frac{2}{3}\) 也就是每次移動花費2個記憶體操作時間
實作步驟如下
- 檢查
head是否為NULL以及透過list_empty這個函式檢查鏈結串列是否為空的 - 設定一個指標
front往next的方向移動，另一個back往prev的方向移動 - 當兩者交會之際及為中點
- 再將其刪除即可
修改過後的程式碼也在下方的 完整程式碼
- 圖解說明
-
快慢指標
- 初始位置
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> head [color = purple] turtle -> head [color = green] }- 快指標(rabbit) 移動兩個節點，慢指標(turtle)移動一個節點
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> e2 [color = purple] turtle -> e1 [color = green] }- 最終快指標(rabbit) 移動到了尾端之前，慢指標(turtle) 所指的就是中間節點
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] rabbit [shape=plaintext;label="rabbit"] turtle [shape=plaintext;label="turtle"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 rabbit -> e5 [color = purple] turtle -> e3 [color = green] } -
反向迭代
- 初始位置
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front"] back [shape=plaintext;label="back"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> head [color = purple] back -> head [color = green] }- 前指標(front) 往前移動一個節點，後指標(back) 往後移動一個節點
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front"] back [shape=plaintext;label="back"] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> e1 [color = purple] back -> e5 [color = green] }- 當兩個指標交錯或是相遇時，便可找到中間節點
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="bear"] e2 [label="dolphin"] e3 [label="gerbil"] e4 [label="..."] e5 [label="meerkat"] front [shape=plaintext;label="front", rank=max] back [shape=plaintext;label="back", rank=max] //prev [shape=plaintext;label="prev"] //curr [shape=plaintext;label="curr"] //next [shape=plaintext;label="next"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 //prev -> head //curr -> e1 [color=red] //next -> e1 front -> e3 [color = purple] back -> e3 [color = green] }
-
完整程式碼
- 修改後的 （反向迭代）
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 *front = head->next, *back = head->prev;
if (front == back)
return false;
while (front != back && front->next != back) {
back = back->prev;
if (back == front || front->next == back)
break;
front = front->next;
}
element_t *node = list_entry(front->next, element_t, list);
list_del(&node->list);
q_release_element(node);
return true;
}
- 原先的 （快慢指標）
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 *rabbit = head, *turtle = head;
do {
rabbit = rabbit->next->next;
if (rabbit == head->prev || rabbit == head) {
break;
}
turtle = turtle->next;
} while (!(rabbit == head->prev) && !(rabbit == head));
element_t *node = list_entry(turtle->next, element_t, list);
list_del(&node->list);
q_release_element(node);
return true;
}
q_delete_dup
根據要求，需要將鏈結串列中有重複字串的節點刪除，可以從 82. Remove Duplicates from Sorted List II 中對於題目的敘述得知，head 所指的鏈結串列是已經 Sorted ，因此只需要考慮重複的節點會是相鄰的即可，也就是下面的第一張圖的情況
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="Head"]
e1 [label="1"]
e2 [label="2", color=lightblue2 style=filled]
e3 [label="2", color=lightblue2 style=filled]
e4 [label="4"]
e5 [label="5"]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
digraph ele_list {
rankdir=LR;
node[shape=record];
head [label="Head"]
e1 [label="1"]
e2 [label="2", color=lightblue2 style=filled]
e3 [label="3"]
e4 [label="2", color=lightblue2 style=filled]
e5 [label="4"]
// next 方向
head -> e1
e1 -> e2
e2 -> e3
e3 -> e4
e4 -> e5
e5 -> head
// prev 方向
head -> e5
e5 -> e4
e4 -> e3
e3 -> e2
e2 -> e1
e1 -> head
// pointer 初始化
}
- 實作流程
- 檢查
head是否為NULL, 透過list_empty這個函式檢查鏈結串列是否為空的以及使用list_is_singular這個函式來檢查鏈結串列是否只有head與一個節點 - 設定一個旗標變數
flag並給予初始值 0，他的用途是檢測字串是否有出現重複 - 使用
list_for_each_entry_safe來走訪每個節點，使用str這個變數來儲存下一個節點的字串內容 - 若是下一個節點不是鏈結串列的
head並且目前節點與下一個節點的字串不一致且flag為 0 就進行正常迭代，若是flag為 1，就刪除目前的節點 - 若是下一個節點的字串與當前節點的字串一致的話，就刪除目前的節點，並且把旗標變數
flag設定為 1，接著進行迭代 - 完成走訪後回傳
true
- 檢查
完整程式碼
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
if (list_empty(head) || list_is_singular(head))
return true;
element_t *node, *safe;
bool flag = 0;
list_for_each_entry_safe (node, safe, head, list) {
char *str = list_entry(node->list.next, element_t, list)->value;
if (node->list.next != head && !strcmp(str, node->value)) {
list_del(&node->list);
q_release_element(node);
flag = 1;
} else if (flag) {
list_del(&node->list);
q_release_element(node);
flag = 0;
}
}
return true;
}
q_swap
根據要求，需要將鏈結串列中的兩兩一對位置交換，從 24. Swap Nodes in Pairs 可以得知，我們僅能交換節點的位置來達成目的，並不可以透過更改節點的字串的指標來完成。
-
實作流程
- 檢查
head是否為NULL，並且透過list_is_sigular這個函式來判斷使否需要進行 swap - 設定兩
list_head的指標，分別指向head->next(以下稱為後者) 與head->next->next(以下稱為前者) - 使用
for-loop進行迭代，需要進行以下步驟- 使用
list_del將前者與鏈結串列斷開連結 - 將後者的
prev指派給前者的prev - 將後者指派給前者的
next - 將前者指派給後者的
prev->next - 將前者指派給後者的
prev
- 使用
- 檢查
-
圖解說明
- 設定兩個相鄰的指標，分別為後者
back = head->next與前者front = back->next
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 斷開前者
front的與鏈結串列的連結
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 //e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 //e2 -> e1 e1 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 將
back的prev指派給front的prev
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 //e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 將
front的next指向back
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e1 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 將
front指派給back的prev->next
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e2 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> head e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 將
front指派給back的prev
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="2"] e5 [label="4"] back [shape=plaintext;label="back"] front [shape=plaintext;label="front"] // next 方向 head -> e2 e1 -> e3 e2 -> e1 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e1 e1 -> e2 e2 -> head // pointer 初始化 back -> e1 [color=green] front -> e2 [color=purple] }- 完成一次交換，將
back與frnot都往前移動兩個節點
- 設定兩個相鄰的指標，分別為後者
TODO
在聽過老師的 Code Review 之後，發現 q_swap 與 q_reverseK 是可以共用程式碼的，因此想要找時間比較目前的 q_swap 與 直接呼叫 q_reverseK 的效能差異
完整程式碼
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_is_singular(head))
return;
struct list_head *node, *next;
for (node = head->next, next = node->next; node != head && next != head;
node = node->next, next = node->next) {
list_del(next);
next->prev = node->prev;
next->next = node;
node->prev->next = next;
node->prev = next;
}
}
q_reverse
根據要求，需要將鏈結串列中的節點反向連接，並且不可以使用 q_insert_head 或是 q_remove_head 這類有 malloc 或是 free 的指令。 可以從 206. Reverse Linked List 完成 Single-Linked_list 的解法，再將其延伸到環狀雙向的版本
struct ListNode *reverseList(struct ListNode *head)
{
if (!head || !head->next)
return head;
struct ListNode *ret = malloc(sizeof(struct ListNode));
ret->val = head->val;
ret->next = NULL;
head = head->next;
while (head)
{
struct ListNode *tmp = ret;
ret = head;
head = head->next;
ret->next = tmp;
}
return ret;
}
-
實作流程
- 檢查
head是否為NULL，並且透過list_empty檢查是否為空的鏈結串列 - 使用
list_head的指標，分別是before,current,after - 使用
while-loop進行迭代，迭代過程中需要進行以下幾個步驟會使用 Graphviz進行表示
- 檢查
-
圖解說明
- 設定三個指標分別是
before = head->prev,current = head,after = NULL
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> NULL [color=purple] }- 進入
while-loop，直到after指到head為止 - 把
after指向current->next
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> e1 [color=purple] }- 把
current->next指派到before，current->prev指派到after
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [color = red;label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [color = red; label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> e5 [color=green] current -> head [color=orange] after -> e1 [color=purple] }- 把
current指派給beforedigraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> head [color=green] current -> head [color=orange] after -> e1 [color=purple] } - 把
after指派給currentdigraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] before [shape=plaintext;label="before"] current [shape=plaintext;label="current"] after [shape=plaintext;label="after"] // next 方向 head -> e5 [label="next"] e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> head // prev 方向 head -> e1 [label="prev"] e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 before -> head [color=green] current -> e1 [color=orange] after -> e1 [color=purple] } - 接著利用
while-loop迭代即可
- 設定三個指標分別是
完整程式碼
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *before = head->prev, *current = head, *after = NULL;
while (after != head) {
after = current->next;
current->next = before;
current->prev = after;
before = current;
current = after;
}
}
q_reverseK
根據要求， reverseK 是 reverse 與 swap 的混合體。在一條鏈結串列中，每 K 個元素進行 reverse ，若是 K 的值大於剩下的節點數，就不做任何的改變。
在實作當中會使用到以下兩個在 list.h 中所定義的函式
- list_cut_position
這個函式的用途是把一條鏈結串列切成兩條
-
傳入的引數
- head_to : 被切下的
linked_list所要接入的點 - head_from : 被切下的
linked_list的前一個節點 - node : 被切下的
linked_list的點
- head_to : 被切下的
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
- list_splice
把 linled_list 插入到另外一條中
static inline void list_splice(struct list_head *list, struct list_head *head)
{
struct list_head *head_first = head->next;
struct list_head *list_first = list->next;
struct list_head *list_last = list->prev;
if (list_empty(list))
return;
head->next = list_first;
list_first->prev = head;
list_last->next = head_first;
head_first->prev = list_last;
}
- list_splice_init
static inline void list_splice_init(struct list_head *list,
struct list_head *head)
{
list_splice(list, head);
INIT_LIST_HEAD(list);
}
-
實作流程
- 檢查
head是否為NULL，並且透過list_empty檢查是否為空的鏈結串列以及使用list_is_singular確保鏈結串列裡面有不只一個節點 - 因為要使用
list_cut_position這個函式，所以我們先使用LIST_HEAD這個巨集建立一個新的 list_head - 因為會將鏈結串列切開，所以要使用
list_for_each_safe這個函式來完成迭代 - 設定一個變數
num，當num等於k的時候，就執行剪下K個節點，並且reverse，最終再將其接回原本的點。 - 重複步驟(4)直到鏈結串列的尾端
- 檢查
-
圖解說明
- 主要講解置換的過程，首先先宣告三個指標
node,safe,tmp = head
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head ->e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head // pointer 初始化 tmp -> head }- 利用巨集
LIST_HEAD建立一個新list-head的head
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head }- 假設
k目前為 3 ，也就是list_for_each_safe進行三次迭代才會開始進行切斷…等等動作，下圖展示的是第三次迭代
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e1 e1 -> e2 e2 -> e3 e3 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] node0 -> e3 [color=green] safe -> e4 [color=purple] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e3 e3 -> e2 e2 -> e1 e1 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head }- 首先先使用巨集切出第二條鏈結串列
list_cut_position(&new_head, tmp, node);，從tmp得下一個節點到node切下後貼去new_head，可以看到下面變成兩條鏈結串列了
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e4 e1 -> e2 e2 -> e3 e3 -> new_head e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> e1 node0 -> e3 [color=green] safe -> e4 [color=purple] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> head e3 -> e2 e2 -> e1 e1 -> new_head new_head -> e3 // pointer 初始化 tmp -> head }- 將
new_head進行reverse
digraph ele_list { rankdir=LR; node[shape=record]; //head [label="Head"] new_head [label="new_head"] e1 [label="3"] e2 [label="2"] e3 [label="1"] //e4 [label="4"] //e5 [label="5"] //e6 [label="6"] //e7 [label="7"] node0 [shape=plaintext;label="node"] //safe [shape=plaintext;label="safe"] //tmp [shape=plaintext;label="tmp"] // next 方向 //head -> e4 e1 -> e2 e2 -> e3 e3 -> new_head //e4 -> e5 //e5 -> e6 //e6 -> e7 //e7 -> head new_head -> e1 node0 -> e1 [color=green] //safe -> e4 [color=purple] // prev 方向 //head -> e7 //e7 -> e6 //e6 -> e5 //e5 -> e4 //e4 -> head e3 -> e2 e2 -> e1 e1 -> new_head new_head -> e3 // pointer 初始化 //tmp -> head }- 將
new_head插入tmp之後，再初始化new_head
digraph ele_list { rankdir=LR; node[shape=record]; head [label="Head"] new_head [label="new_head"] e1 [label="1"] e2 [label="2"] e3 [label="3"] e4 [label="4"] e5 [label="5"] e6 [label="6"] e7 [label="7"] node0 [shape=plaintext;label="node"] safe [shape=plaintext;label="safe"] tmp [shape=plaintext;label="tmp"] // next 方向 head -> e3 e3 -> e2 e2 -> e1 e1 -> e4 e4 -> e5 e5 -> e6 e6 -> e7 e7 -> head new_head -> new_head [shape=plaintext;label = "next"] // prev 方向 head -> e7 e7 -> e6 e6 -> e5 e5 -> e4 e4 -> e1 e1 -> e2 e2 -> e3 e3 -> head new_head -> new_head [shape=plaintext;label = "prev"] // pointer 初始化 tmp -> head safe -> e4 node0 -> e3 }- 最後再將
tmp移動到safe的前一個，便完成了一次的迭代
- 主要講解置換的過程，首先先宣告三個指標
完整程式碼
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *node, *safe, *tmp = head;
LIST_HEAD(new_head);
int num = 0;
list_for_each_safe (node, safe, head) {
++num;
if (num == k) {
list_cut_position(&new_head, tmp, node);
q_reverse(&new_head);
list_splice_init(&new_head, tmp);
num = 0;
tmp = safe->prev;
}
}
}
q_sort
根據要求，需要將鏈結串列進行由小到大排序。這題參考自 你所不知道的 C 語言: linked list 和非連續記憶體 中的Merge_Sort 以及 陳日昇 同學的實作。
-
實作流程
-
q_merge
- 檢查
head是否為NULL，並且透過list_empty檢查是否為空的鏈結串列 - 將環狀結構斷開
- 把
head->next作為merge_divide的引數以及函式回傳值 - 當由有到大後，每個節點的
prev都是亂掉的以及環狀結構尚未接回，因此要走訪每個節點，並且把prev都接上，最後再把尾端接回head
- 檢查
-
merge_divide
- 檢查
head是否為NULL，並且檢查head->next是否NULL，若是就直接回傳head - 使用上面所使用過的 快慢指標 來找到中點
- 將中點切開成兩條獨立的
list_head，再呼叫自己進行迭代 - 將每個節點都切開後傳入
merge_two_nodes
- 檢查
-
merge_two_nodes
- 利用 indirect pointer 來進行每個節點的走訪
- 逐一比較
left與right的字串大小 - 最後若是其中一方已經到盡頭，便會直接把餘剩的一方接在排序完的尾端
-
圖解說明
merge_divide這個函式主要在進行下面橘色框框的動作，而merge_two_nodes是在進行藍色及綠色框框
digraph G {
compound=true
node[shape=box, height=.1];sorted_1 sorted_2 sorted_3 sorted_4 sorted_5 sorted_6 sorted_7 sorted_8;
node[shape=record, height=.1];input result
divide_41 divide_42 divide_21 divide_22 divide_23 divide_24
merge_21 merge_22 merge_23 merge_24 merge_41 merge_42;
input[label="<f0>2|<f1>5|<f2>4|<f3>6|<f4>8|<f5>1|<f6>7|<f7>3"]
result[label="<f0>1|<f1>2|<f2>3|<f3>4|<f4>5|<f5>6|<f6>7|<f7>8"]
divide_41[label="<f1>2|<f2>5|<f3>4|<f4>6"]
divide_42[label="<f1>8|<f2>1|<f3>7|<f4>3"]
divide_21[label="<f0>2|<f1>5"]
divide_22[label="<f0>4|<f1>6"]
divide_23[label="<f0>8|<f1>1"]
divide_24[label="<f0>7|<f1>3"]
sorted_1[label="1"]
sorted_2[label="2"]
sorted_3[label="3"]
sorted_4[label="4"]
sorted_5[label="5"]
sorted_6[label="6"]
sorted_7[label="7"]
sorted_8[label="8"]
merge_21[label="<f0>2|<f1>5"]
merge_22[label="<f0>4|<f1>6"]
merge_23[label="<f0>1|<f1>8"]
merge_24[label="<f0>3|<f1>7"]
merge_41[label="<f1>2|<f2>4|<f3>5|<f4>6"]
merge_42[label="<f1>1|<f2>3|<f3>7|<f4>8"]
subgraph cluster_0 {
style=filled;
color="#ef6548";
label="divide";
divide_pad[label="----------------------", style=invis]
divide_pad -> divide_23[style=invis]
input -> divide_41
input -> divide_42
divide_41 -> divide_21
divide_41 -> divide_22
divide_42 -> divide_23
divide_42 -> divide_24
}
divide_21:f0 -> sorted_2
divide_21:f1 -> sorted_5
divide_22 -> sorted_4
divide_22 -> sorted_6
divide_23:f0 -> sorted_8
divide_23:f1 -> sorted_1
divide_24:f0 -> sorted_7
divide_24:f1 -> sorted_3
subgraph cluster_1 {
style=filled;
color="#a6cee3";
label="sorted lists";
sorted_1;
sorted_2;
sorted_3;
sorted_4;
sorted_5;
sorted_6;
sorted_7;
sorted_8;
}
sorted_2 -> merge_21:f0
sorted_5 -> merge_21:f1
sorted_4 -> merge_22:f0
sorted_6 -> merge_22:f1
sorted_8 -> merge_23:f1[constraint=false]
sorted_1 -> merge_23:f0
sorted_7 -> merge_24:f1
sorted_3 -> merge_24:f0
subgraph cluster_2 {
style=filled;
color="#b2df8a";
label="merge";
merge_pad[label="--------------------", style=invis]
rank=same; merge_41; merge_pad; merge_42
rank=same; merge_41; merge_42; merge_pad;
merge_22 -> merge_pad[style=invis]
merge_23 -> merge_pad[style=invis]
merge_pad -> result[style=invis]
merge_21 -> merge_41
merge_22 -> merge_41
merge_23 -> merge_42
merge_24 -> merge_42
merge_41 -> result
merge_42 -> result
}
}
完整程式碼
struct list_head *merge_two_nodes(struct list_head *left,
struct list_head *right)
{
struct list_head *new_head = NULL, **indirect = &new_head, **iter = NULL;
for (; left && right; *iter = (*iter)->next) {
iter = strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) >= 0
? &right
: &left;
*indirect = *iter;
indirect = &(*indirect)->next;
}
*indirect = (struct list_head *) ((uint64_t) left | (uint64_t) right);
return new_head;
}
struct list_head *merge_divide(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *rabbit = head, *turtle = head, *middle;
for (; rabbit && rabbit->next;
rabbit = rabbit->next->next, turtle = turtle->next)
;
middle = turtle;
// cut off the link
turtle->prev->next = NULL;
struct list_head *left = merge_divide(head);
struct list_head *right = merge_divide(middle);
return merge_two_nodes(left, right);
}
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
// cut off the link
head->prev->next = NULL;
head->next = merge_divide(head->next);
struct list_head *before = head, *after = head->next;
for (; after != NULL; after = after->next) {
after->prev = before;
before = after;
}
before->next = head;
head->prev = before;
}
q_descend
Leetcode 解法
struct ListNode *reverseList(struct ListNode *head)
{
if (!head || !head->next)
return head;
struct ListNode *ret = malloc(sizeof(struct ListNode));
ret->val = head->val;
ret->next = NULL;
head = head->next;
while (head)
{
struct ListNode *tmp = ret;
ret = head;
head = head->next;
ret->next = tmp;
}
return ret;
}
struct ListNode* removeNodes(struct ListNode* head){
head = reverseList(head);
struct ListNode *node = head, *node_next = node->next;
while(node_next != NULL){
if(node_next->val >= node->val){
node = node->next;
node_next = node_next->next;
} else {
node->next = node_next->next;
node_next = node_next->next;
}
}
head = reverseList(head);
return head;
}
這題 leetcode 解法是參考自 Youtube 影片中所講解的第二種思路(Approach 2)
由於 Leetcode 是單向的 linked_list 因此由左邊比較到右邊較為複雜，因此這題的關鍵點就在於 reverse ，只要先將原本的鏈結串列 reverse ，就可以方便地進行比較所有節點大小的動作，最後再將鏈結串列 reverse 即可達成要求
而實作 q_descend 的時候就更為方便，因為使用的是環狀雙向鏈結串列，可以不須經過反向，直接透過 prev 操作即可，以下為實作流程
- 實作流程
- 檢查 head 是否為 NULL，並且透過 list_empty 檢查是否為空的鏈結串列
- 使用
list_head的指標node指向head->prev以及node_prev指向node->prev - 利用
list_entry各別取得佇列內的資料 - 接著反向走訪所有節點，假如
ndoe的字串比node_prev的字串還小的時候，就不進行移除節點，將兩個節點都分別往prev的方向移動一格 - 若是
ndoe的字串比node_prev的字串還大，就將node_prev移除(delete)，然後再進行下一輪的走訪
完整程式碼
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
int num = 0;
struct list_head *node = head->prev, *node_prev = node->prev;
element_t *que = list_entry(node, element_t, list);
element_t *que_prev = list_entry(node_prev, element_t, list);
while (&que_prev->list != head) {
if (strcmp(que->value, que_prev->value) < 0) {
que_prev = list_entry(que_prev->list.prev, element_t, list);
que = list_entry(que->list.prev, element_t, list);
++num;
} else {
list_del(&que_prev->list);
q_release_element(que_prev);
que_prev = list_entry(que->list.prev, element_t, list);
}
}
return ++num;
}
q_merge
根據要求，傳入的 head 為 queue_contex_t 的 head ，因此也會需要將節點往 next 移動一格才開始存取每個queue 的 head。 他可以視作 merge sort 的延伸版，透過已經實作好的merge_two_nodes 這個函式，可以把兩段長度不相同的鏈結串列由小至大合併，因此只需要將每個 queue 的 head 都加入後便可以把所有的點併入一條
- 實作流程
- 檢查
head是否為NULL，並且透過list_empty檢查是否為空的鏈結串列 - 取得第一條
queue的節點個數，再走訪每個queue_contex_t的q - 在每個走訪的過程，都先將每條鏈結串列變成非環狀的，再使用
merge_two_nodes這個函式將兩條鏈結串列合併成一條 - 使用
INIT_LIST_HEAD將每個空的head都指向自己，避免出錯 - 最後的作法與
q_sort的實作一樣，需要將 每個節點的prev都接回，並且把它接回環狀的
- 檢查
完整程式碼
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
int num = 0;
struct list_head *master = list_entry(head->next, queue_contex_t, chain)->q;
num += q_size(master);
master->prev->next = NULL;
struct list_head *node = head->next->next;
while (node != head) {
struct list_head *slave = list_entry(node, queue_contex_t, chain)->q;
num += q_size(slave);
slave->prev->next = NULL;
master->next = merge_two_nodes(master->next, slave->next);
INIT_LIST_HEAD(slave);
node = node->next;
}
struct list_head *before = master, *after = master->next;
for (; after != NULL; after = after->next) {
after->prev = before;
before = after;
}
before->next = master;
master->prev = before;
return num;
}
研讀 Linux 核心原始程式碼的 lib/list_sort.c
先去取得 lib/list_sort.c，接著開始研讀程式碼，因為怕篇幅太長超過限制，因此，我將研讀的筆記額外放在這Lab0 lib/list_sort.c 學習筆記
將 list_sort.c 加入專案
接下來要將 list_sort 加入專案中
- 將 list_sort.c 加入至與
queue.c同個層級的目錄 - 將 list_sort.h 這個標頭檔也加入跟原始檔一樣層級的目錄下
- 因為會使用到
unlikely與likely這樣的巨集，因此需要將 compiler.h 中的這兩行加入list_sort.h中
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
- 在
list_sort.c的檔案中，有使用到u8這樣的型別，所以也將其以巨集的方式定義在list_sort.h下
#include <stdint.h>
typedef uint8_t u8;
- 接著修改
Makefile中 OBJS，新增一個list_sort.o
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
- linenoise.o web.o
+ linenoise.o web.o list_sort.o
- 最後修改
qtest.c這個檔案- 加入
include "list_sort.h" - 設定一個變數決定是否使用 list_sort
static int use_list_sort = 0;- 編寫一個比較的函式
static int cmp(void* priv, const struct list_head *l1, const struct list_head *l2) { return strcmp(list_entry(l1, element_t, list)->value, list_entry(l2, element_t, list)->value); }- 根據該該所設定的變數決定是否使用 list_sort ，於是著手修改
do_sort中的執行 sort的部份
if (current && exception_setup(true)) use_list_sort ? list_sort(NULL, current->q, cmp): q_sort(current->q); exception_cancel();- 最後在將我們所將入的參數使用
add_param加入help的選單中
add_param("listsort", &use_list_sort, "Use the sort which is made by linux kernel developers", NULL); - 加入
可以看到下方的 option 有多了 listsort 這個選項
cmd> help
Commands:
# ... | Display comment
dedup | Delete all nodes that have duplicate string
descend | Remove every node which has a node with a strictly greater value anywhere to the right side of it
dm | Delete middle node in queue
free | Delete queue
help | Show summary
ih str [n] | Insert string str at head of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
it str [n] | Insert string str at tail of queue n times. Generate random string(s) if str equals RAND. (default: n == 1)
log file | Copy output to file
merge | Merge all the queues into one sorted queue
new | Create new queue
next | Switch to next queue
option [name val] | Display or set options. See 'Options' section for details
prev | Switch to previous queue
quit | Exit program
reverse | Reverse queue
reverseK [K] | Reverse the nodes of the queue 'K' at a time
rh [str] | Remove from head of queue. Optionally compare to expected value str
rt [str] | Remove from tail of queue. Optionally compare to expected value str
show | Show queue contents
shuffle | Shuffle all the nodes in the queue in a random method
size [n] | Compute queue size n times (default: n == 1)
sort | Sort queue in ascending order
source | Read commands from source file
swap | Swap every two adjacent nodes in queue
time cmd arg ... | Time command execution
web [port] | Read commands from builtin web server
Options:
echo 1 | Do/don't echo commands
entropy 0 | Show/Hide Shannon entropy
error 5 | Number of errors until exit
fail 30 | Number of times allow queue operations to return false
length 1024 | Maximum length of displayed string
listsort 0 | Use the sort which is made by linux kernel developers
malloc 0 | Malloc failure probability percent
simulation 0 | Start/Stop simulation mode
verbose 4 | Verbosity level
貼心提醒(x) 採雷實錄(o)
在使用 clang-format -i 的時候，記得不要對 Makefile 使用
安裝 perf
由於我的電腦是這學期重灌到 ubuntu-22.04 的，所以效能測試工具 perf 需要重新下載，跟著老師的筆記一步一步即可，不過這邊要特別注意，我們一般安裝的 kernel.perf_event_paranoid 會是 4 ，可以透過
$ cat /proc/sys/kernel/perf_event_paranoid
來進行查看，但是我們如果想要把權限全部打開的話，必須使用這條指令
$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"
來將權限值設為 -1
再來可以輸入 $ perf top 來確認自己是否有拿到最高權限值
進行效能比較
在 trace 這個目錄下創建一個新的測試命令集 trace-sort.cmd ，裡面的測試如下
# Test performance of sort betweem q_sort() and list_sort()
# You can modify the option listsort and the RAND to meet your need
option listsort 0
new
it RAND 500000
time
sort
time
接著執行它
$ ./qtest -f traces/trace-sort.cmd
就可以得到
$ ./qtest -f traces/trace-sort.cmd
# Test performance of sort betweem q_sort() and list_sort()
# You can modify the option listsort and the RAND to meet your need
l = []
l = [uivpdik xfbkwkz gmbzaf ysygwrx vkssukdk ongishsxd jhxbjqsny dmxgkd iocxyll adojbg btznx equevnb fpxfr ldurei mbolzsokz gaviuvdl ylifpbvs cawtwi mxyyk ytova aihdgcca dhhcjjyvb bxldmra iovvqwa ftogdizpo ouham nlbkp mwwxth ihpymm rxxlvju ... ]
Elapsed time = 0.167, Delta time = 0.167
l = [aaaaizu aaabrr aaabvyd aaacf aaacgxla aaacpcf aaacqqfg aaacwmp aaadqam aaaeo aaahahyow aaahi aaajzhtau aaamxvbgy aaano aaaoge aaaqpjab aaaryjsxv aaatohdfj aaatolb aaavjefox aaavtfpgc aaavuwipm aaawrad aaaxx aaaycpd aaayh aaaykau aaazhb aaaztnh ... ]
Elapsed time = 0.601, Delta time = 0.435
Freeing queue
可以看到我們使用了 qtest 中的 time 功能，來取得我們執行 sort 所花費的時間，最後的那個 Delta time 就是我們所希望得到的
接著開始比較 q_sort 與 list_sort 這兩個排序的效能差別
我們分別測試資料比數從 10 萬筆資料到 100 萬筆資料
並且重複做三次
| 資料數 | 1. q_sort() | 2. q_sort() | 3. q_sort() | 平均 |
|---|---|---|---|---|
| 10 萬筆 | 0.038 | 0.036 | 0.039 | 0.038 |
| 20 萬筆 | 0.095 | 0.089 | 0.096 | 0.093 |
| 30 萬筆 | 0.198 | 0.192 | 0.218 | 0.203 |
| 40 萬筆 | 0.313 | 0.309 | 0.340 | 0.321 |
| 50 萬筆 | 0.440 | 0.427 | 0.491 | 0.453 |
| 60 萬筆 | 0.556 | 0.592 | 0.616 | 0.588 |
| 70 萬筆 | 0.697 | 0.702 | 0.762 | 0.720 |
| 80 萬筆 | 0.846 | 0.831 | 0.901 | 0.859 |
| 90 萬筆 | 0.975 | 0.960 | 0.996 | 0.976 |
| 100 萬筆 | 1.123 | 1.098 | 1.119 | 1.113 |
| 資料數 | 1. list_sort() | 2. list_sort() | 3. list_sort() | 平均 |
|---|---|---|---|---|
| 10 萬筆 | 0.023 | 0.023 | 0.023 | 0.023 |
| 20 萬筆 | 0.069 | 0.064 | 0.060 | 0.064 |
| 30 萬筆 | 0.129 | 0.124 | 0.132 | 0.128 |
| 40 萬筆 | 0.213 | 0.220 | 0.216 | 0.216 |
| 50 萬筆 | 0.296 | 0.290 | 0.290 | 0.290 |
| 60 萬筆 | 0.411 | 0.401 | 0.392 | 0.401 |
| 70 萬筆 | 0.498 | 0.507 | 0.505 | 0.503 |
| 80 萬筆 | 0.645 | 0.611 | 0.600 | 0.619 |
| 90 萬筆 | 0.708 | 0.680 | 0.708 | 0.699 |
| 100 萬筆 | 0.805 | 0.808 | 0.791 | 0.801 |
可以看到他 list_sort 比起 q_sort 的效能大約都好了 30% ~ 40%
接下來使用 perf 這個工具來看更詳細的對比資料
根據老師的筆記，可以使用以下指令來取得 cache-misses, cache-references, instructions, cycles 這些項目的資訊
$ perf stat --repeat 10 -e cache-misses,cache-references,instructions,cycles ./qtest -f trace/trace-sort.cmd
這條指令會重複跑10次 ./qtest -f trace/trace-sort.cmd 這個命令，並且將我們所設定要取得的資訊統計出來，如下面所列
Performance counter stats for './qtest -f traces/trace-sort.cmd' (10 runs):
20,633,385 cache-misses # 34.793 % of all cache refs ( +- 0.15% )
58,757,193 cache-references ( +- 0.76% )
2,275,963,009 instructions # 0.93 insn per cycle ( +- 0.02% )
2,400,840,346 cycles ( +- 0.57% )
0.53341 +- 0.00388 seconds time elapsed ( +- 0.73% )
接著，我因為覺得每次都要打這麼長的命令很不人性化，因此我將它加入 Makefile 裡面
export cycle ?= 5
perf: qtest
perf stat --repeat $(cycle) -e cache-misses,cache-references,instructions,cycles ./qtest -f traces/trace-sort.cmd
這樣以後只要輸入 make perf 就可使用了
接著來比較兩者的差異在 50萬 比資料下的狀況
| 項目 | q_sort | list_sort |
|---|---|---|
| cache-misses | 27,057,256 | 20,610,754 |
| cache-references | 75,094,812 | 59,647,674 |
| % of all caches refs | 35.770 % | 34.833 % |
| instructions | 2,292,705,155 | 2,276,127,334 |
| cycles | 3,545,449,526 | 2,488,046,136 |
| insn per cycle | 0.70 | 0.95 |
可以看到 list_sort 在 cache-misses 的數量上少了將近 35% ，這樣該就是老師在作業提示這邊所說的，linux kernel 開發者有針對 cache 來做演算法的設計，因此才可以減少這麼多的 cache-misses，並且同時也減少了 instructions ，所以 list_sort 的 IPC 會比起 q_sort 好 35%
在 qtest 提供新的命令 shuffle
根據 Fisher–Yates shuffle 演算法的概念，可以得知該演算法的實作步驟分為以下幾點
- 實作步驟
- 取得一個 N 個的鏈結串列，並且運用
q_size取的節點個數 - 隨機產生一個介於1到剩餘節點的數字 R
- 從最小的開始數，將第 R 個數字移動到自己這條鏈結串列的尾端
- 重複 (2) 到 (3) 的步驟
- 當節點個數 == 0 的時候，便是
shuffle完成之際
- 取得一個 N 個的鏈結串列，並且運用
觀察 lab0-c 的檔案結構可以知道如果要加入新的命令需修改 qtest.c 這個檔案，首先先實作 q_shuffle 這個功能
/* Shuffle all the nodes in the queue in a random method */
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
int num = q_size(head);
struct list_head *node = head->next;
while (num != 0) {
// step 2
int random = rand() % num;
for (int i = 0; i < random; ++i)
node = node->next;
// step 3
list_del(node);
list_add_tail(node, head);
node = head->next;
--num;
}
}
當主要的功能實作完成之後，再來需要的就是將執行他的函式實作出來，這邊主要進行的就是引數的檢查, 還有啟用 set_noallocate_mode 這個功能後，就開始執行 q_shuffle ，再來就是判斷是否執行超過時間，最後再將 set_noallocate_mode 取消啟用即可，回傳值使用 q_show(3)
接著開始研究 q_show 這個函式，假如們希望印出正確的回應 ( 例如 l = [ a b c d e ] ) ，就必須要通過像是雙向環狀或是非 NULL 這樣的條件，才可以透過第893行將正確的值輸出
static bool q_show(int vlevel)
{
bool ok = true;
if (verblevel < vlevel)
return true;
int cnt = 0;
if (!current || !current->q) {
report(vlevel, "l = NULL");
return true;
}
if (!is_circular()) {
report(vlevel, "ERROR: Queue is not doubly circular");
return false;
}
report_noreturn(vlevel, "l = [");
struct list_head *ori = current->q;
struct list_head *cur = current->q->next;
if (exception_setup(true)) {
while (ok && ori != cur && cnt < current->size) {
element_t *e = list_entry(cur, element_t, list);
if (cnt < BIG_LIST_SIZE) {
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value);
if (show_entropy) {
report_noreturn(
vlevel, "(%3.2f%%)",
shannon_entropy((const uint8_t *) e->value));
}
}
cnt++;
cur = cur->next;
ok = ok && !error_check();
}
}
...
}
經過上述，我們可以實作出 do_shuffle 這個函式
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
set_noallocate_mode(true);
if (current && exception_setup(true))
q_shuffle(current->q);
exception_cancel();
set_noallocate_mode(false);
return q_show(3);
}
使用 Valgrind 排除 qtest 實作的記憶體錯誤
首先研讀了老師的作業提示以 Valgrind 分析記憶體問題，可以知道 Valgrind 這個工具的強大
並且我們只要在終端機輸入
$ make valgrind
就可以執行 Makefile 內預先寫好的腳本，以下是 Makefile 中關於 valgrind 的部份
valgrind_existence:
@which valgrind 2>&1 > /dev/null || (echo "FATAL: valgrind not found"; exit 1)
valgrind: valgrind_existence
# Explicitly disable sanitizer(s)
$(MAKE) clean SANITIZER=0 qtest
$(eval patched_file := $(shell mktemp /tmp/qtest.XXXXXX))
cp qtest $(patched_file)
chmod u+x $(patched_file)
sed -i "s/alarm/isnan/g" $(patched_file)
scripts/driver.py -p $(patched_file) --valgrind $(TCASE)
@echo
@echo "Test with specific case by running command:"
@echo "scripts/driver.py -p $(patched_file) --valgrind -t <tid>"
可以看上面的 valgrind_existence 是用來檢查是否安裝了 valgrind
接著繼續看到 valgrind 的腳本，可以看到它會利用 mktemp 建立一個暫存的檔案，接著複製檔案過去，再幫該檔案加上所有使用者( +a )都可以執行( +x )的權限
這邊我認為在 chmod u+x $(patched_file) 這行指令應該要使用 root 權限，從鳥高私房菜-改變權限, chmod 這篇文章中的範例來看，要執行 chmod 操作是需要切換到 root 身份的。所以我覺得這行應該改為 sudo chmod u+x $(patched_file) 會比較恰當，或是在執行 make 腳本時要使用 sudo make valgrind 。
提交 pull request?
jserv
後來詳細觀察了檔案權限以及程式碼，發現是我搞錯了，加上 sudo 會使得編譯出的檔案變成僅限 root 權限的，在之後的刪除 make clean 會產生問題，下次會再更加謹慎的。錯誤的提交
接著執行 make valgrind ，可以發現執行的速度下降了許多，符合老師所提及的
最後發現並沒有洩漏的記憶體
接著使用 Massif 視覺化工具
可以在 valgrind 使用的參數列表中加入 --tool=massif
$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd
就可以得到一張 massif.out.XXXXX，其中的 XXXXX 會是一串數字
接著要去massif-visualizer 安裝 massif-visualizer桌面版
接著輸入
$ massif-visualizer massif.out.XXXXX
就可以得到 massif 記憶體分析的圖了!
開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤
根據 Makefile 中關於 Sanitizer 的部份，可以看到
# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
# https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
LDFLAGS += -fsanitize=address
endif
若是執行 make 的時候一起加上了 SANITIZER=1 這樣的參數就可以開啟 Sanitizer，來檢查程式碼
Sanitizer 與 Valgrind 是不可以同時使用的，所以假如在 make 的時候有加上了SANITIZER=1 這樣的參數的話，就要記得先執行 make clean 清除先前所編譯好的才能正常使用 Valgrind
SANITIZER 使用步驟如下:
$ make SANITIZER=1
$ make test
// 若是沒有報錯就可以清除
$ make clean
研讀論文〈Dude, is my code constant time?〉
論文筆記
原本針對程式碼的偵測工具，是針對不同的硬體所設計的，因此換了一個平台，例如不同的 CPU 或是 micro-code 更新，原本的工具就沒有辦法使用了，為此，這篇文章提出了基於統計機率的方法來檢測程式碼。
論文使用的方法是 TIMING LEAKAGE DETECTION，首先測量兩個不同輸入數據類型的執行時間，然後檢查這兩個時間分布是否在統計上不同
- Measure execution time
反覆測量我們所使用的函數 (在 lab0-c 中就是it,ih,rh及rt) 對屬於兩個不同輸入資料類型的輸入的執行時間。- Classes definition
這邊主要在定義所使用的類別為兩種不同類型的，第一種為固定的資料類別，另外一種為隨機的資料類別 - Cycle counters
使用 CPU 自帶的週期計數器，在 X86-64 平台下可以使用RDTSC，而在 aarch64 平台下可以使用mrs個暫存器搭配內嵌組合語言的方式來呈現，詳情可以看這裡 - Environmental conditions
為了最小化環境變化對結果的影響，每次測量都對應於一個隨機選擇的類別，特別注意 ： 類別分配和輸入準備任務在測量階段之前完成
- Classes definition
- Apply post-processing
- Cropping
典型的時序分佈對較長的執行時間呈正偏斜。這可能是由於測量不準確、被作業系統或其他外部活動中斷造成的。在這種情況下，可以透過裁剪測量的數據來避免誤差 - Higher-order preprocessing
- Cropping
- Apply statistical test
- t-test
使用 Welch’s t-test 這個方法進行檢測，這個測試方法也是 dudect 所使用的 - Non-parametric tests
虛無假說可以參考這裡
- t-test
提出的改進方法
可以知道從原始的實作來看，PERCENTILE 可以去除掉極端值，但是在 leb0-c 並沒有相關的實作，因此這會是其中一個改變的方向。 再來是上面所提到的 Classes definition ，在 lab0-c 的實作中， 固定資料的字串是用 0 來進行填充的，但是 0 在 ascii 碼中代表的是 '\0' ，這與字串的結尾符號一致，所以這可能會導致問題。 再來是在 measure 這個函式中，使用了兩個 int 來保存插入或是移除前後的個數是否為正確的，但是這樣的檢查僅只有確認個數，但卻沒有明確知道它是否為插入在頭尾…等等，因此這也是一個問題
故目前發現的問題為
- PERCENTILE
- 隨機 / 固定生成字串的結尾符號
- q_size() 的使用不恰當
根據上述所提的問題，實施相對應的實作
- PERCENTILE
首先因為老師原本的參數是散裝的，但在原本的 dudect 中是使用 struct 來包住許多的參數
int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
所以我把上面替換成下面，這邊的 struct 也與原本的有所不同，原本的 ticks 是儲存在同一個陣列的，但我改成像是原本的定義，分成 before_ticks 與 after_ticks 。
typedef struct {
int64_t *before_ticks;
int64_t *after_ticks;
int64_t *exec_times;
uint8_t *input_data;
uint8_t *classes;
dudect_config_t *config;
ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
int64_t *percentiles;
} dudect_ctx_t;
同時也新增了關於 percenteils 相關的巨集以及函式
特別注意，因為我把上述這些參數都改成 struct 了，所以相關函式的引數都要進行更改。
- 隨機 / 固定生成字串的結尾符號
可以看到原本的老師對於 fix string 的部份是以 0 來進行 memset 的填充，但是在 ascii 碼中， 0 代表的是 '\0'，也就是字串的結尾符號，我認為在這邊不應該使用結尾符號來進行填充，所以我將 'a' 填充進去，並且在字串的結尾使用 '\0' 。同理，在隨機生成的的話，就會需要避免隨機產生的數字為 0 ，所以我將隨機生成的數字加上了 65，以避免這問題。
void prepare_inputs(uint8_t *input_data, uint8_t *classes)
{
randombytes(input_data, N_MEASURES * CHUNK_SIZE);
for (size_t i = 0; i < N_MEASURES; i++) {
classes[i] = randombit();
if (classes[i] == 0) {
memset(input_data, 'a', CHUNK_SIZE - 1);
input_data[CHUNK_SIZE - 1] = '\0';
} else {
uint8_t rand;
for (size_t i = 0; i < CHUNK_SIZE - 1; i++) {
randombytes(&rand, 1);
input_data[i] = (rand % 50) + 65;
}
input_data[CHUNK_SIZE - 1] = '\0';
}
}
}
- q_size() 的使用不恰當
在 measure 這個函式中，以 insert_tail 這個函式為例
...
case DUT(insert_tail):
for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
char *s = get_random_string();
dut_new();
dut_insert_head(
get_random_string(),
*(uint16_t *) (input_data + i * CHUNK_SIZE) % 10000);
int before_size = q_size(l);
before_ticks[i] = cpucycles();
dut_insert_tail(s, 1);
after_ticks[i] = cpucycles();
int after_size = q_size(l);
dut_free();
if (before_size != after_size - 1)
return false;
}
break;
...
可以看到它取得了插入前後的 q_size()，並且相減來比對是否有插入，但是這樣的檢查僅能檢查出是否有插入成功，並不能知道它是否插在尾巴，所以這個檢查的操作我就先將其移除，畢竟在 make test 的前面也有檢查過 insert head 等等的功能了。
在經過這樣的修改過後， make test 就可以得到 100 分了
TODO
把 lab0-c/dudect 下的檔案整理的好看一些
-
Any changes
Be notified of any changes
-
Mention me
Be notified of mention me
-
Unsubscribe
Subscribe