# 2025q1 Homework1 (lab0)
contributed by < `Denny0097` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```shell
$ 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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU family: 6
Model: 165
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 5
BogoMIPS: 5808.02
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clfl
ush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc arch_p
erfmon rep_good nopl xtopology cpuid pni pclmulqdq ssse3 fma cx16 pdcm pcid
sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm
3dnowprefetch invpcid_single ssbd ibrs ibpb stibp ibrs_enhanced fsgsbase bmi
1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt xsaveopt xsavec xge
tbv1 xsaves md_clear flush_l1d arch_capabilities
Virtualization features:
Hypervisor vendor: Microsoft
Virtualization type: full
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 2 MiB (8 instances)
L3: 16 MiB (1 instance)
Vulnerabilities:
Gather data sampling: Unknown: Dependent on hypervisor status
Itlb multihit: KVM: Mitigation: VMX unsupported
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknow
n
Reg file data sampling: Not affected
Retbleed: Mitigation; Enhanced IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-
eIBRS SW sequence; BHI SW loop, KVM SW loop
Srbds: Unknown: Dependent on hypervisor status
Tsx async abort: Not affected
```
## 針對佇列操作的程式碼實作
### q_new
```c
struct list_head *q_new()
{
// struct list_head *head = malloc(sizeof(struct list_head));
// if (head)
// INIT_LIST_HEAD(head);
// return head;
element_t *node = malloc(sizeof(element_t));
if (node)
INIT_LIST_HEAD(&(node->list));
return &node->list;
}
```
->
```c
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
```
### q_free
```c
/* Free all storage used by queue */
void q_free(struct list_head *head)
{
struct list_head *del = NULL;
for(struct list_head *cur = head->next; cur!=head; cur=cur->next)
{
if(cur)
del = cur;
free(list_entry(del, element_t, list));
}
if (head)
free(list_entry(head, element_t, list));
}
```
->
```c
if (!head)
return;
struct list_head *cur, *safe;
list_for_each_safe(cur, safe, head) {
list_del(cur);
q_release_element(list_entry(cur, element_t, list));
}
free(head);
```
->
```c
if(!head)
return;
element_t *cur, *safe;
list_for_each_entry_safe (cur, safe, head, list) {
list_del(&cur->list);
q_release_element(cur);
}
free(head);
```
### q_insert_head
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if(head){
struct list_head *new = q_new();
char *newV = list_entry(new, element_t, value);
newV = s;
head->prev = new;
new->next = head;
return true;
}
return false;
}
```
### q_insert
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
node->value = malloc((strlen(s) + 1) * sizeof(char));
strncpy(node->value, s, strlen(s) + 1);
list_add(&node->list, head);
return true;
}
```
# Test of malloc failure on insert_head
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-12-malloc 0/6
+++ TESTING trace trace-13-malloc:
### q_remove_head
```c
/* Insert an element at head of queue */
if (!head || list_empty(head))
return NULL;
element_t *pos = list_entry(head->next, element_t, list);
strncpy(sp, pos->value, bufsize);
list_del_init(&pos->list);
return NULL;
```
->
```c
if (!head || list_empty(head))
return NULL;
element_t *pos = list_entry(head->next, element_t, list);
if (sp && bufsize)
{
strncpy(sp, pos->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(&pos->list);
return pos;
```
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
ERROR: Probably not constant time or wrong implementation
Testing insert_head...(7/10)
ERROR: Probably not constant time or wrong implementation
Probably constant time
ERROR: Probably not constant time or wrong implementation
--- trace-17-complexity 0/5
--- TOTAL 23/100
### q_delete_mid
```c
if (!head||list_empty(head))
return false;
int size = q_size(head);
struct list_head *del = head->next;
int pos = 1;
while (pos < size/2)
{
del = del->next;
pos ++;
}
list_del(del);
q_release_element(list_entry(del, element_t, list));
return true;
```
->
```c
if (!head || list_empty(head))
return false;
struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward && forward->next != backward) {
forward = forward->next;
backward = backward->prev;
}
list_del(forward);
q_release_element(list_entry(forward, element_t, list));
return true;
```
### q_delete_dup
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
bool del = false;
struct list_head *cur, *next;
list_for_each_safe (cur, next, head) {
element_t *entry = list_entry(cur, element_t, list);
if (next != head &&
!strcmp(entry->value, list_entry(next, element_t, list)->value)) {
list_del(cur);
q_release_element(entry);
del = true;
} else if (del) {
list_del(cur);
q_release_element(entry);
del = false;
}
}
return true;
}
```
### q_swap
#### Leetcode 24
``` c
if (!head||!head->next)
return head;
struct ListNode *newHead = head->next;
struct ListNode *prev = NULL;
struct ListNode *cur = head;
while (cur&&cur->next)
{
struct ListNode *pair = cur->next;
cur->next = pair->next;
pair->next = cur;
if (prev)
prev->next = pair;
prev = cur;
cur = cur->next;
}
return newHead;
```
->
```c
if (!head || !head->next)
return;
struct list_head *prev = head;
struct list_head *cur = head->next;
head->next = head->next->next;
do {
struct list_head *pair = cur->next;
cur->next = pair->next;
pair->next->prev = cur;
pair->next = cur;
cur->prev = pair;
prev->next = pair;
pair->prev = prev;
prev = cur;
cur = cur->next;
} while (cur != head && cur != head->prev);
```
### q_reverse
pointer ver:
```c
head = head -> prev;
struct list_head *cur = NULL, *temp = NULL;
for (cur = head; cur != head -> prev ; cur = cur->next)
{
temp = cur->next;
cur->next = cur->prev;
cur->prev = temp;
}
temp = cur->next;
cur->next = cur->prev;
cur->prev = temp;
```
error: head just a list but head->prev in a entry
->
```c
// X head = head -> prev;
```
Indirect pointer ver:
```c
```
### q_reverseK
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head) || k < 2)
return;
struct list_head *cur = head ->next;
while (cur != head)
{
struct list_head *front = cur, *tail = NULL, *prev = NULL;
int count = 0;
while (count < k && cur != head)
{
cur = cur->next;
count ++;
}
if (count < k)
return;
tail = cur->prev;
prev = front->prev;
front->prev = tail;
tail->next = front;
q_reverse(front);
prev->next = tail;
tail->prev = prev;
front->next = cur;
cur->prev = front;
}
}
```
### q_ascend
```c
struct list_head *prevBig = head;
struct list_head *currBig = head->next;
for (struct list_head *cur = head->next; cur != head; cur = cur->next)
{
if (list_entry(currBig, element_t, list)->value
< list_entry(cur, element_t, list)->value)
{
currBig = cur;
struct list_head *pos = currBig->prev;
while (pos != prevBig)
{
struct list_head *del = pos;
pos = pos->next;
list_del(del);
}
prevBig = currBig;
}
}
return 0;
```
error: 因為currBig在遇到更小的情況不會更新，導致ㄏcurrBig沒有達到預期作用
```
l = [2 3 1]
cmd> ascend
l = [ ... ]
ERROR: Queue has more than 0 elements
cmd> ih 2
l = [2 ... ]
ERROR: Queue has more than 1 elements
```
deal: 改成current Min，遇到更大的就更新改成current Min並del小的，遇到更小的就單純更新current Min
->
```c
if (!head || list_empty(head))
return 0;
struct list_head *currMin = head->next;
int elementNum = q_size(head);
for (struct list_head *cur = currMin->next; cur != head; cur = cur->next)
{
if (list_entry(currMin, element_t, list)->value
< list_entry(cur, element_t, list)->value)
{
list_del(currMin);
q_release_element(list_entry(currMin, element_t, list));
elementNum --;
}
currMin = cur;
}
return elementNum;
```
```
l = [c d b a]
cmd> ascend
ERROR: At least one node violated the ordering rule
```
->誤會題意，我以為是到比左邊小的數字時左邊的數字就不會再被刪除，結果是要保證右邊比左邊大，看錯的有點離譜
改成用prev去找，比較小就del，確保ascend
```c
if (!head || list_empty(head))
return 0;
int elementNum = q_size(head);
char *min = list_entry(head->prev, element_t, list)->value;
struct list_head *cur = head->prev;
while (cur != head) {
if (strcmp(min, list_entry(cur, element_t, list)->value) > 0) {
struct list_head *del = cur;
cur = cur->prev;
element_t *entry = list_entry(del, element_t, list);
list_del(del);
q_release_element(entry);
elementNum--;
}
else {
min = list_entry(cur, element_t, list)->value;
cur = cur->prev;
}
}
return elementNum;
```
### infineted loop Error
```
l = [10 9 9 10]
cmd> ascend
ERROR: At least one node violated the ordering rule
l = [9 9 10]
cmd> ascend
ERROR: At least one node violated the ordering rule
l = [9 9 10]
Error limit exceeded. Stopping command execution
cmd> ascend
cmd>
cmd> quit
cmd> free
cmd>
cmd>
cmd>
cmd> free
cmd> quit
cmd>
cmd>
```
strcmp使用錯誤
->
```c
(strcmp(min, list_entry(cur, element_t, list)->value) < 0)
```
### q_sort
一開始想要先把head切掉在去處理分開的queue，因為遇到malloc error，所以用多一個function merge_sort()，但不太直覺，遇到很多困難。
```c
// cut left and right as two independent qeueu
// sort
merge_sort(left, right, descend);
// connect to head
```
#### merge_sort
```c
if (q_size(left)>1) {
// merge_sort(head, false);
// merge_sort(right, false);
// merge(head, right, descend);
}
```
#### merge
```c
if(descend) {
while(curOfLeft != right) {
if(strcmp(list_entry(curOfLeft, element_t, list)->value,
list_entry(curOfRight, element_t, list)->value) >= 0) {
list_add_tail(left, curOfLeft);
curOfLeft = curOfLeft->next;
}else {
list_add_tail(left, curOfRight);
curOfRight = curOfRight->next;
}
}
}
else {
while(curOfLeft != right) {
if(strcmp(list_entry(curOfLeft, element_t, list)->value,
list_entry(curOfRight, element_t, list)->value) <= 0) {
list_add_tail(left, curOfLeft);
curOfLeft = curOfLeft->next;
}else {
list_add_tail(left, curOfRight);
curOfRight = curOfRight->next;
}
}
}
```
改成利用struct list_head left來分割queue，可以避開不能malloc的問題，有點太習慣使用pointer差點忘記原本的結構就是可以宣告的。
#### merge
```c
struct list_head *curOfLeft = left->next;
struct list_head *curOfRight = head->next;
struct list_head *nextOps = NULL;
struct list_head result;
INIT_LIST_HEAD(&result);
while (curOfLeft != left && curOfRight != head && descend) {
if (strcmp(list_entry(curOfLeft, element_t, list)->value,
list_entry(curOfRight, element_t, list)->value) < 0) {
nextOps = curOfRight->next;
list_move_tail(curOfRight, &result);
curOfRight = nextOps;
} else {
nextOps = curOfLeft->next;
list_move_tail(curOfLeft, &result);
curOfLeft = nextOps;
}
}
while (curOfLeft != left && curOfRight != head && !descend) {
if (strcmp(list_entry(curOfLeft, element_t, list)->value,
list_entry(curOfRight, element_t, list)->value) > 0) {
nextOps = curOfRight->next;
list_move_tail(curOfRight, &result);
curOfRight = nextOps;
} else {
nextOps = curOfLeft->next;
list_move_tail(curOfLeft, &result);
curOfLeft = nextOps;
}
}
if (list_empty(left)) {
// Append remaining nodes from left
list_splice_tail_init(head, &result);
} else {
// Append remaining nodes from right
list_splice_tail_init(left, &result);
}
list_splice_tail_init(&result, head);
```
### sort
```c
if (!head || list_empty(head) || head->next->next == head)
return;
// find mid
struct list_head *forward = head->next, *backward = head->prev;
while (forward != backward && forward->next != backward) {
forward = forward->next;
backward = backward->prev;
}
struct list_head left;
struct list_head *mid = forward;
list_cut_position(&left, head, mid);
q_sort(&left, descend);
q_sort(head, descend);
merge(head, &left, descend);
```
簡化merge的判斷，可以讓code更簡潔。
#### merge
```c
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return q_size(head);
queue_contex_t *first = list_entry(head->next, queue_contex_t, chain);
struct list_head *node = head->next->next;
while (node != head) {
queue_contex_t *cur = list_entry(node, queue_contex_t, chain);
if (cur->q) {
merge(first->q, cur->q, descend);
}
node = node->next;
}
return first->size;
```
## 研讀 lib/list_sort.c
Sign in with Wallet
Connect another wallet