HackMD
2022q1 Homework1 (lab0)
contributed by < Chao-Shun-Cheng >
實驗環境
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8700K CPU @ 3.70GHz
Stepping: 10
CPU MHz: 3700.000
CPU max MHz: 4700.0000
CPU min MHz: 800.0000
BogoMIPS: 7399.70
Virtualization: VT-x
L1d cache: 192 KiB
L1i cache: 192 KiB
L2 cache: 1.5 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-11
作業要求
q_new: 建立新的「空」佇列q_free: 釋放佇列所佔用的記憶體q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點q_release_element: 釋放特定節點的記憶體空間q_size: 計算目前佇列的節點總量q_delete_mid: 移走佇列中間的節點，詳見 LeetCode 2095. Delete the Middle Node of a Linked Listq_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 LeetCode 82. Remove Duplicates from Sorted List IIq_swap: 交換佇列中鄰近的節點，詳見 LeetCode 24. Swap Nodes in Pairsq_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點q_sort: 以遞增順序來排序鏈結串列的節點
開發過程
queue.c 實作
queue 資料結構
從 queue.h 當中的 element_t 可以知道 Node 的資料結構包含一個 value 與 list 。其中 value 會指向一個字串，另外 list 則是會定義在 list.h 裡的一種資料結構。可以看到 list 有兩個指標分別指向下一個與上一個 Node 的 list。
typedef struct {
char *value;
struct list_head list;
} element_t;
struct list_head {
struct list_head *prev;
struct list_head *next;
};
完整的 queue 資料結構如下圖所示。
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
q_new
new 需要先透過 malloc 進行記憶體配置，再透過 list.h 所提供的 INIT_LIST_HEAD 去進行初始化。
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head) {
INIT_LIST_HEAD(head);
return head;
} else {
return NULL;
}
}
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
q_free
首先要判斷 queue 裡面是否存在節點，可以利用 list.h 提供的 list_empty 去判斷。如果有 Node 再利用 list_first_entry 去得到指向包含這個 list 的 element。最後再利用 q_release_element 去釋放 Node 的記憶體。
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *target = list_first_entry(l, element_t, list);
list_del(l->next);
q_release_element(target);
}
free(l);
}
其中 list_first_entry 是利用 container_of 去獲得 Node 的記憶體位置，詳細使用方法與原理可以參考 Linux 核心原始程式碼巨集: container_of。
q_insert_head
首先要先利用 malloc 去分配 Node 所需要的記憶體空間，再去分配 value 所需要的空間，最後再利用 list.h 所提供的 list_add 將 Node 插入 queue 當中。
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newh = malloc(sizeof(element_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
list_add(&newh->list, head);
return true;
}
q_insert_tail
與 q_insert_head 方法雷同，不同的是利用 list_add_tail 去插入佇列中。
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *newh = malloc(sizeof(element_t));
if (!newh)
return false;
int len = strlen(s);
newh->value = malloc(sizeof(char) * (len + 1));
if (!newh->value) {
free(newh);
return false;
}
strncpy(newh->value, s, len + 1);
list_add_tail(&newh->list, head);
return true;
}
q_remove_head
首先透過 list_first_entry 去獲得指向第一個 Node 的指標，再透過 list_del 去將 Node 移出 queue。需要特別注意的是 value 與 bufsize 的大小，以及結尾字元 \0。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *target = list_first_entry(head, element_t, list);
list_del(head->next);
int len = strlen(target->value);
if (len > (bufsize - 1)) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, target->value, len);
sp[len] = '\0';
}
return target;
}
q_remove_tail
與 q_remove_head 雷同，不過是透過 list_last_entry 去獲得指向最後一個 Node 的指標。
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head) || !sp)
return NULL;
element_t *target = list_last_entry(head, element_t, list);
list_del(head->prev);
int len = strlen(target->value);
if (len > (bufsize - 1)) {
strncpy(sp, target->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, target->value, len);
sp[len] = '\0';
}
return target;
}
q_size
這邊是直接用 list_for_each 走訪全部節點以計算數量。還在思考如何降低計算時間。
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *node = NULL;
int size = 0;
list_for_each (node, head) {
size++;
}
return size;
}
q_delete_mid
宣告兩個指標 next_node 與 prev_node 用 while 分別從 queue 的前與後去走，當 prev_node == next_node 或 next_node->next == prev_node 就代表找到中間的 Node 了。
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *next_node = head->next, *prev_node = head->prev;
while (next_node != prev_node && next_node->next != prev_node) {
next_node = next_node->next;
prev_node = prev_node->prev;
}
element_t *target = list_entry(prev_node, element_t, list);
list_del(prev_node);
q_release_element(target);
return true;
}
q_delete_dup
這題主要是參考 LeetCode 82. Remove Duplicates from Sorted List II 這題的內容來實作，不過在原題目中是有重複的要全部 delete ，因此我透過 list_for_each_safe 去看每個 Node 的值，並將值用 value 指標指著，再透過strcmp(value, target->value) == 0 來去判斷鄰近的 Value 是不是一樣，是的話就 delete ，直到遇到不一樣為止。
Case one : 沒有遇到相同
value 直接可以指到下一個值
Case two : 有遇到相同
delete 後面重複出現的之後，還要再刪掉自己本身
Version one
考慮刪掉自己本身的 Node ，但發現 trace-06 一直過不了。
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
struct list_head *node = NULL, *safe = NULL;
bool dup = false;
char *value = NULL;
element_t *target = NULL;
list_for_each_safe (node, safe, head) {
target = list_entry(node, element_t, list);
if (strcmp(value, target->value) == 0) { // duplicates
list_del(node);
q_release_element(target);
dup = true;
} else {
value = target->value;
if (dup) {
target = list_entry(node->prev, element_t, list);
list_del(node->prev);
q_release_element(target);
dup = false;
}
}
}
return true;
}
Version two
於是嘗試不刪掉自己本身，指刪掉後面一樣的 Node ，竟然神奇的過了。不確定是不是我對題目有誤解還是有甚麼 Bug 。
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return false;
bool dup = false;
char *value = NULL;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (value && strcmp(value, entry->value) == 0) {
list_del(&entry->list);
q_release_element(entry);
dup = true;
} else {
value = entry->value;
if (dup) {
// target = list_entry(entry->list.prev, element_t, list);
// list_del(&target->list);
// q_release_element(target);
dup = false;
}
}
}
return true;
}
q_swap
swap 這邊是利用 from 與 to 兩個指標分別去紀錄要 swap 兩個 Node 的前後關係，再透過 while 去把所有需要 swap 的 Node 進行相關的指標替換即可。
void q_swap(struct list_head *head)
{
if (!head || list_is_singular(head))
return;
struct list_head *node = head->next, *from = NULL, *to = NULL, *next = NULL;
while ((node != head) && (node->next != head)) {
next = node->next;
from = node->prev;
to = node->next->next;
from->next = next;
next->prev = from;
next->next = node;
node->prev = next;
node->next = to;
to->prev = node;
node = to;
}
}
q_reverse
這邊的想法是直接將 prev 與 next 兩個指標的內容交換即可。因此直接透過 list_for_each_safe 去把每個 Node 裡的 prev 與 next 內容交換。
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node = NULL, *safe = NULL, *temp = NULL;
list_for_each_safe (node, safe, head) {
temp = node->next;
node->next = node->prev;
node->prev = temp;
}
temp = head->next;
head->next = head->prev;
head->prev = temp;
}
q_sort
這邊是利用 mergesort 下去進行排序，並透過 LIST_HEAD 將變數放在 stack 裡，就不用特別去思考如何釋放記憶體的議題。雖然測資可以通過，但當我要 git commit 時發現，queue.h 不能修改。會去研讀 list_sort.c 並進一步思考如何修改。
後來發現將 Function 放在 q_sort 上面就可以直接使用，不用特別在宣告在 queue.h 裡面，總算可以順利 git commit 了。
mergesort 主要有兩個重點，分別是將 list 切開以及合併，合併這邊參考 LeetCode 21. Merge Two Sorted Lists 的思考下去實作。
void mergetwolist(struct list_head *head1,
struct list_head *head2,
struct list_head *head)
{
if (!head || !head1 || !head2 || (list_empty(head1) && list_empty(head2)))
return;
if (list_empty(head1)) {
list_splice_tail_init(head2, head);
return;
}
if (list_empty(head2)) {
list_splice_tail_init(head1, head);
return;
}
struct list_head *temp = NULL, *l1 = head1->next, *l2 = head2->next;
while (l1 != head1 && l2 != head2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) > 0) {
temp = l2;
l2 = l2->next;
list_move_tail(temp, head);
} else {
temp = l1;
l1 = l1->next;
list_move_tail(temp, head);
}
}
list_splice_tail_init(head1, head);
list_splice_tail_init(head2, head);
}
切分的部分則是利用區域變數的特性，離開函式會自動釋放記憶體的優勢，來去進行實作。
void mergesort(struct list_head *head, int size)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
LIST_HEAD(head1);
LIST_HEAD(head2);
int mid = size >> 1, count = 0;
struct list_head *node = NULL, *safe = NULL;
list_for_each_safe (node, safe, head) {
count++;
if (count == mid) {
list_cut_position(&head1, head, node);
list_splice_tail_init(head, &head2);
break;
}
}
mergesort(&head1, mid);
mergesort(&head2, size - mid);
mergetwolist(&head1, &head2, head);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
mergesort(head, q_size(head));
}
make test 自動評分
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ 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
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
花了一些時間與參考許多同學的實作方式，總算是看到皮卡丘了 QAQ
文字訊息不要用螢幕截圖展現，你的讀者可能是視障朋友，而且圖片無助於資料檢索。
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
已經修正，感謝老師提醒
