contributed by < JoshuaLee0321
>
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.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: 43 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 2600X Six-Core Processor
CPU family: 23
Model: 8
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
Frequency boost: enabled
CPU max MHz: 3600.0000
CPU min MHz: 2200.0000
BogoMIPS: 7199.10
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht
HackMD 提供時間戳記,不需要自行列舉。
注意作業書寫規範:中英文間用一個半形空白字元區隔。
好的
queue.c
的過程q_new
malloc
分配空間給queue,考量到malloc
有機會出錯,那先判斷是不是沒有分配成功,之後再利用 Linux 核心中的 INIT_LIST_HEAD
來把指針指向自己struct list_head *q_new()
{
struct list_head *head = malloc(1 * sizeof(struct list_head));
if(!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
q_free
list_for_each_safe
run 過所有的 item,一個一個節點 release 但這樣會出先 segmentation fault改進你的漢語描述。
void q_free(struct list_head *l)
{
if (!l || list_empty(l)) {
free(l);
return;
}
struct list_head *it,*safe;
list_for_each_safe(it, safe, l){
element_t *tmp = list_entry(it, element_t, list);
list_del(it);
free(tmp);
}
free(list_entry(l, element_t, list));
return;
}
後續改成 q_release_element
的內建API
void q_free(struct list_head *l)
{
if(!l || list_empty(l)) return;
// ~~ struct list_head *it, *safe;
// list_for_each_safe(it, safe, l){
// q_release_element(it);
// }~~
/*以上為錯誤版本,已修正成以下版本*/
list_for_each_entry_safe(it, safe, l, list) {
q_release_element(it);
}
free(l)
}
更正版本:
element_t *it = NULL, *safe = NULL;
list_for_each_entry_safe(it, safe, l, list) { q_release_element(it); }
(更新)發現 safe 並沒有初始化成NULL 導致出錯,已修正
(更新)發現 list_for_each_entry_safe 以及 q_release_element 才可以把東西刪除完全
q_insert_head
q_insert_tail
q_delete_head
q_delete_tail
(更)剛開始的實做如下,但這樣會發生我的實做並不是constant time,錯誤還有代釐清
(更)以上課後學習到的新知 (macro) function 為基準 重新製作了 q_insert_##type 在macro 中
(更)已把 q_insert 以及 q_remove 類型的都把它做成macro 方便維護,除此之外還找到了 q_remove_macro
中少加入 if(list_empty(head)) 而導致 segmentation fault
#define q_insert_macro(type, func) \
bool q_insert_##type(struct list_head *head, char *s) \
{ \
if (!head) \
return false; \
element_t *new_node = malloc(1 * sizeof(*new_node)); \
if (!new_node) \
return false; \
new_node->value = malloc((strlen(s) + 1) * sizeof(char)); \
if (!new_node->value) { \
q_release_element(new_node); \
return false; \
} \
memcpy(new_node->value, s, strlen(s) + 1); \
func(&new_node->list, head); \
return true; \
} \
#define q_remove_macro(type, func) \
element_t *q_remove_##type(struct list_head *head, char *sp, \
size_t bufsize) \
{ \
if (!head || list_empty(head)) \
return NULL; \
element_t *del = func(head, element_t, list); \
list_del(&del->list); \
if (sp != NULL) { \
memcpy(sp, del->value, bufsize - 1); \
sp[bufsize - 1] = '\0'; \
} \
return del; \
}
而實際上我就可以只利用四行程式碼來實作
/* Insert an element at head of queue */
q_insert_macro(head, list_add);
/* Insert an element at tail of queue */
q_insert_macro(tail, list_add_tail);
/* Remove an element from head of queue */
q_remove_macro(head, list_first_entry);
/* Remove an element from tail of queue */
q_remove_macro(tail, list_last_entry);
q_delete_dup
linux/list.h
中的 API 跑過迴圈;要注意的事情是,這個function 必須把重複的東西通通刪除掉。由於list_for_each_safe
中的 safe
可以當作 next
來使用,如此一來我們只要
head
中的所有元素it
來觀察是否當前元素與下個元素相同bool not_finished
變數來記錄是否要把當前 it
刪除bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_is_singular(head))
return false;
struct list_head *it, *safe = NULL;
bool not_finished = false;
list_for_each_safe (it, safe, head) {
element_t *prev = list_entry(it, element_t, list);
element_t *cur = list_entry(safe, element_t, list);
if (!strcmp(prev->value, cur->value)) {
not_finished = true;
list_del(it);
q_release_element(prev);
if (safe->next == (head)) {
list_del(safe);
q_release_element(cur);
break;
}
} else if (not_finished) {
not_finished = false;
list_del(it);
q_release_element(prev);
}
}
return true;
}
q_size
jserv
老師撰寫好了int q_size(struct list_head *head)
{
if (!head) return 0;
int len = 0;
struct list_head *li;
list_for_each(li,head)
len++;
return len;
}
q_delete_mid
queue
的長度除以2之後給定一個int cnt
去計算這個list目前到哪裡,但這個實做方法有一個問題,它會花到O(2N)的時間
size
的時間single_p
以及每一次會往後走兩步的 double_p
,在double走到底的時候single會直接在中間
single_p
給移除掉即可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 *single_p, *double_p;
single_p = double_p = head->next;
while(double_p != (head) && double_p->next != (head)) {
single_p = single_p->next;
double_p = double_p->next->next;
}
list_del_init(single_p);
q_release_element(list_entry(single_p,element_t,list));
return true;
}
q_swap
swap-nodes-in-pairs
中,可以使用 iterative
跟 recursive
的方法實做,而因為有linux kernel 的 API,我選擇使用 iterative
的作法
it
當作 每一次走過的nodeit
往前走一步it
跟 it->next
互換void q_swap(struct list_head *head)
{
if(!head || list_empty(head) || head->next->next == head) return;
struct list_head *it = head->next;
while(it != (head) && it->next != (head)) {
list_move(it,it->next);
it = it->next;
}
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
q_reverse
q_reverse
如果使用 Linux 核心的 api 就會非常簡單
void q_reverse(struct list_head *head)
{
if(!head || list_empty(head) || list_is_singular(head)) return;
struct list_head *it, *safe = NULL;
list_for_each_safe(it, safe, head) {
list_move(it, head);
}
return;
}
q_sort
Valgrind
# Explicitly disable sanitizer(s)
$ make clean SANITIZER=0 qtest
make[1]: Entering directory '/home/joshua/linux2023/lab0-c'
rm -f 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 .qtest.o.d .report.o.d .console.o.d .harness.o.d .queue.o.d .random.o.d .dudect/constant.o.d .dudect/fixture.o.d .dudect/ttest.o.d .shannon_entropy.o.d .linenoise.o.d .web.o.d *~ qtest /tmp/qtest.*
rm -rf .dudect
rm -rf *.dSYM
(cd traces; rm -f *~)
CC qtest.o
CC report.o
CC console.o
CC harness.o
CC queue.o
CC random.o
CC dudect/constant.o
CC dudect/fixture.o
CC dudect/ttest.o
CC shannon_entropy.o
CC linenoise.o
CC web.o
LD qtest
make[1]: Leaving directory '/home/joshua/linux2023/lab0-c'
cp qtest /tmp/qtest.83iQ10
chmod u+x /tmp/qtest.83iQ10
sed -i "s/alarm/isnan/g" /tmp/qtest.83iQ10
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind
--- 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, remove_head, reverse and merge
--- 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, sort, descend and reverseK
--- 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
Test with specific case by running command:
scripts/driver.py -p /tmp/qtest.83iQ10 --valgrind -t <tid>
目前一直卡在 q_insert 的function 並沒有在constant time 處理完畢
除此之外,每一次free佇列都會發生一些問題
(更新) 發先是 q_free 中的safe 沒有初始化
測試時一直發現 trace - 17 一直報告不是常數時間。同時我也很確定我的實作方法為constant time,而經由閱讀 KHLEE 的實作方法,更改了 dudect/constant.c 以及 dudect/fixture 的計算方法後才得到目前的滿分