HackMD
2025q1 Homework1 (lab0)
contributed by < DivaGabriel >
開發環境
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 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): 4
On-line CPU(s) list: 0-3
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-6500 CPU @ 3.20GHz
CPU family: 6
Model: 94
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 3
CPU(s) scaling MHz: 93%
CPU max MHz: 3600.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc
art arch_perfmon pebs bts rep_good nopl xtopology nons
top_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor
ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm p
cid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_tim
er aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch
cpuid_fault pti ssbd ibrs ibpb stibp tpr_shadow flexp
riority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2
smep bmi2 erms invpcid mpx rdseed adx smap clflushopt
intel_pt xsaveopt xsavec xgetbv1 xsaves dtherm ida ara
t pln pts hwp hwp_notify hwp_act_window hwp_epp vnmi m
d_clear flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-3
Vulnerabilities:
Gather data sampling: Vulnerable: No microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Mitigation; PTE Inversion; VMX conditional cache flush
es, SMT disabled
Mds: Mitigation; Clear CPU buffers; SMT disabled
Meltdown: Mitigation; PTI
Mmio stale data: Mitigation; Clear CPU buffers; SMT disabled
Reg file data sampling: Not affected
Retbleed: Mitigation; IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prct
l
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointe
r sanitization
Spectre v2: Mitigation; IBRS; IBPB conditional; STIBP disabled; RS
B filling; PBRSB-eIBRS Not affected; BHI Not affected
Srbds: Mitigation; Microcode
Tsx async abort: Mitigation; TSX disabled
開發過程
Commit
原本寫了三、四個函式以後都沒有做git commit導致做的時候跳出一長串訊息不利於修復程式
$ git commit
--- modified queue.c
+++ expected coding style
@@ -65,12 +65,13 @@ bool q_insert_tail(struct list_head *hea
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- if (!head || !head->next) return NULL;
+ if (!head || !head->next)
+ return NULL;
struct list_head *node = head->next;
element_t *entry = list_first_entry(node, element_t, list);
- if (sp && entry->value){
- strncpy(sp,entry->value,bufsize);
- sp[bufsize-1] = '\0';
+ if (sp && entry->value) {
+ strncpy(sp, entry->value, bufsize);
+ sp[bufsize - 1] = '\0';
}
list_del_init(node);
return entry;
@@ -91,7 +92,7 @@ int q_size(struct list_head *head)
int len = 0;
struct list_head *li;
- list_for_each (li, head)
+ list_for_each(li, head)
len++;
return len;
}
@@ -101,15 +102,16 @@ int q_size(struct list_head *head)
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
- if (!head||!head->next) return false;
+ if (!head || !head->next)
+ return false;
struct list_head *slow = head;
struct list_head *fast = head;
struct list_head *cur = NULL;
-
- while(fast && fast->next){
+
+ while (fast && fast->next) {
cur = slow;
- slow = slow->next;
- fast = fast->next->next;
+ slow = slow->next;
+ fast = fast->next->next;
}
cur->next = slow->next;
slow->next->prev = cur;
[!] queue.c does not follow the consistent coding style.
Make sure you indent as the following:
clang-format -i queue.c
Following files need to be cleaned up:
queue.c
Running static analysis...
因此我先把先把裡面清空以後提交了一個初始的commit message上去
Commit 70eb018
queue.c
目前分數: 58/100
q_new()
Commit d8a6790
使用malloc()分配一個list_head節點的空間，若分配失敗則回傳NULL。並且
根據你所不知道的 C 語言: linked list 和非連續記憶體創建新的節點時，初始節點需要指向自己才能保證是一個完整的雙向鏈結串列。
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
head->prev = head;
head->next = head;
return head;
}
Commit fdbed4b
透過查閱queue.h調用INIT_LIST_HEAD()來取代原本的程式碼
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
- head->prev = head;
- head->next = head;
+ INIT_LIST_HEAD(head);
return head;
q_free()
Commit d8a6790
先確認傳進來的節點存在，如果沒有則回傳NULL。再來從head開始遍歷每個節點並刪除。
void q_free(struct list_head *head)
{
if (!head)
return;
struct list_head *cur = head;
struct list_head *nextNode;
while (cur) {
nextNode = cur->next;
free(cur);
cur = nextNode;
}
}
Commit 207dee7
原本的寫法釋放的不是element_t節點，改用list_for_each_entry_safe來去遍歷整個佇列，使用safe來暫存下一個節點的指標，可以使得當entry被刪除時影響遍歷的過程。
if (!head)
return;
- struct list_head *cur = head;
- struct list_head *nextNode;
- while (cur) {
- nextNode = cur->next;
- free(cur);
- cur = nextNode;
- }
+ element_t *entry, *safe;
+ list_for_each_entry_safe(entry, safe, head, list)
+ q_release_element(entry);
+ free(head);
q_insert_head()
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
INIT_LIST_HEAD(&new_node->list);
new_node->value = strdup(s);
list_add(&new_node->list, head);
return true;
}
q_insert_tail()
* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new_node = malloc(sizeof(element_t));
if (!new_node)
return false;
INIT_LIST_HEAD(&new_node->list);
new_node->value = strdup(s);
list_add_tail(&(new_node->list), head);
return true;
}
q_remove_head()
Commit fdbed4b
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || !head->next)
return NULL;
struct list_head *node = head->next;
element_t *entry = list_entry(node, element_t, list);
if (entry->value && sp) {
strncpy(sp, entry->value, bufsize);
sp[bufsize - 1] = '\n';
}
list_del_init(node);
return entry;
}
q_remove_tail()
Commit fdbed4b
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || !head->prev)
return NULL;
struct list_head *node = head->prev;
element_t *entry = list_entry(node, element_t, list);
if (entry->value && sp) {
strncpy(sp, entry->value, bufsize);
sp[bufsize - 1] = '\n';
}
list_del_init(node);
return entry;
}
q_delete_mid()
Commit c1cb992 and 2e9632f
使用快慢指標來讓我找到正中間的節點，再使用list_del_init斷開中間節點的連接,使用list_entry找到節點後釋放它的記憶體。
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 *fast = head->next;
struct list_head *slow = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del_init(slow);
element_t *entry = list_entry(slow, element_t, list);
free(entry);
return true;
}
q_delete_dup()
q_swap()
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head && list_empty(head))
return;
struct list_head *first = head->next;
struct list_head *second = head->next->next;
while (first != head && second != head) {
list_move(first, second);
first = first->next->next;
second = second->next->next;
}
}
q_reverse()
q_reverseK()
q_sort()
q_acend()
q_descend()
q_merge()
+++ TESTING trace trace-02-ops:
# Test of 'q_new', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_remove_tail', and 'q_delete_mid'
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
# Test of 'q_new', 'q_insert_head', 'q_remove_head', 'q_reverse', 'q_sort', and 'q_merge'
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Removed value b != expected value z
ERROR: Removed value a != expected value r
Error limit exceeded. Stopping command execution
--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
# Test of 'q_new', 'q_insert_tail', 'q_insert_head', 'q_remove_head', 'q_size', 'q_swap', and 'q_sort'
ERROR: Removed value dolphin != expected value bear
ERROR: Not sorted in ascending order
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', 'q_size', 'q_swap', and 'q_sort'
ERROR: Removed value gerbil != expected value dolphin
ERROR: Not sorted in ascending order
ERROR: Removed value bear != expected value meerkat
ERROR: Removed value dolphin != expected value fish
ERROR: Removed value meerkat != expected value gerbil
Error limit exceeded. Stopping command execution
--- trace-05-ops 0/6
+++ TESTING trace trace-06-ops:
# Test of 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_delete_dup', 'q_sort', 'q_descend', and 'q_reverseK'
ERROR: Not sorted in ascending order
ERROR: Duplicate strings are in queue or distinct strings are not in queue
ERROR: Removed value c != expected value d
ERROR: Removed value a != expected value c
ERROR: Removed value d != expected value b
Error limit exceeded. Stopping command execution
--- trace-06-ops 0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings: 'q_new', 'q_free', 'q_insert_head', 'q_insert_tail', 'q_remove_head', 'q_reverse', and 'q_sort'
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value meerkat_ != expected value aardvark
ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
--- trace-07-string 0/6
+++ TESTING trace trace-15-perf:
# Test performance of 'q_sort' with random and descending orders: 'q_new', 'q_free', 'q_insert_head', 'q_sort', and 'q_reverse'
# 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
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
ERROR: Not sorted in ascending order
Error limit exceeded. Stopping command execution
--- trace-15-perf 0/6
