# 2025q1 Homework1 (lab0)
contributed by < timsong1 >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
:::spoiler 展開
```
$ 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): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-1035G1 CPU @ 1.00GHz
CPU family: 6
Model: 126
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 5
CPU(s) scaling MHz: 33%
CPU max MHz: 3600.0000
CPU min MHz: 400.0000
BogoMIPS: 2380.80
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 tsc_known_freq pni pclmulqdq
dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16
xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_d
eadline_timer aes xsave avx f16c rdrand lahf_lm abm 3d
nowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_
enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsb
ase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid avx512
f avx512dq rdseed adx smap avx512ifma clflushopt intel
_pt avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec
xgetbv1 xsaves split_lock_detect dtherm ida arat pln p
ts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req v
nmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes v
pclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq r
dpid fsrm md_clear flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 2 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Reg file data sampling: Not affected
Retbleed: Mitigation; Enhanced 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; Enhanced / Automatic IBRS; IBPB conditiona
l; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop,
KVM SW loop
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
:::
## 修改 queue.c
### q_new
>Create an empty queue
```cpp
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head) {
head->prev = head;
head->next = head;
}
return head;
}
```
---
### q_free
>Free all storage used by queue
```cpp
void q_free(struct list_head *head)
{
if (!head)
return;
if (list_empty(head)) {
free(head);
return;
}
while (!list_empty(head)) {
struct list_head *curr = head->next;
list_del(curr);
element_t *element = container_of(curr, element_t, list);
q_release_element(element);
}
free(head);
}
```
### q_insert_head
>Insert an element at head of queue
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
const char *cs = s;
element_t *element = (element_t *) malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(cs);
if (!element->value) {
free(element);
return false;
}
list_add(&element->list, head);
return true;
}
```
### q_insert_tail
>Insert an element at tail of queue
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
const char *cs = s;
element_t *element = (element_t *) malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(cs);
if (!element->value) {
free(element);
return false;
}
list_add_tail(&element->list, head);
return true;
}
```
---
### q_remove_head
>Remove an element from head of queue
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *curr = container_of(head->next, element_t, list);
curr->list.next->prev = head;
head->next = curr->list.next;
curr->list.next = curr->list.prev = NULL;
if (sp && bufsize > 0) {
strncpy(sp, curr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return curr;
}
```
---
### q_remove_tail
>Remove an element from tail of queue
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *curr = container_of(head->prev, element_t, list);
curr->list.prev->next = head;
head->prev = curr->list.prev;
curr->list.next = curr->list.prev = NULL;
if (sp && bufsize > 0) {
strncpy(sp, curr->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return curr;
}
```
---
### q_size
>Return number of elements in queue
```cpp
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
>Delete the middle node in queue
```cpp
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *left, *right;
left = head->prev;
right = head->next;
while (left != right && left->prev != right) {
left = left->prev;
right = right->next;
}
list_del(left);
q_release_element(list_entry(left, element_t, list));
return true;
}
```
---
### q_delete_dup
>Delete all nodes that have duplicate string
>
寫了一個 helper fuction : delete_linked_list() 用來刪除佇列中特定範圍的節點
```cpp
void delete_linked_list(struct list_head *head,
struct list_head *from,
struct list_head *to)
{
struct list_head *node, *safe;
bool flag = false;
list_for_each_safe (node, safe, head) {
if (node == to)
return;
if (node == from)
flag = true;
if (flag) {
list_del(node);
q_release_element(list_entry(node, element_t, list));
}
}
}
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head || list_empty(head))
return false;
if (head->next == head->prev)
return true;
struct list_head *curr = head->next, *next = curr->next;
while (curr != head && next != head) {
const element_t *element = list_entry(curr, element_t, list);
if (strcmp(element->value, list_entry(next, element_t, list)->value) ==
0) {
while (next != head) {
if (strcmp(list_entry(next, element_t, list)->value,
element->value) != 0)
break;
next = next->next;
}
delete_linked_list(head, curr, next);
curr = next;
next = next->next;
continue;
}
curr = curr->next;
next = curr->next;
}
return true;
}
```
---
### q_swap
>Swap every two adjacent nodes
```cpp
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || head->next == head->prev) {
return;
}
struct list_head *curr, *next;
curr = head->next;
next = curr->next;
while (curr != head && next != head) {
curr->prev->next = next; // change the curr and next node
next->next->prev = curr;
curr->next = next->next;
next->prev = curr->prev;
curr->prev = next;
next->next = curr;
curr = curr->next; // move the curr and next pointer forward
next = curr->next;
}
}
```
---
### q_reverse
>Reverse elements in queue
```cpp
void q_reverse(struct list_head *head)
{
if (!head || head->next == head->prev)
return;
struct list_head *node = NULL, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
}
```
---
### q_reverseK
>Reverse the nodes of the list k at a time
```cpp
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
// Assume k is a positive integer and is less than or equal to the length of
// the linked list.
if (!head || head->prev == head->next)
return;
int len = 0;
struct list_head *li = head->next, *start = head, *stop;
while (li != head) {
len++;
if (len == k) {
stop = li->next;
struct list_head *curr = start->next, *next = curr->next,
*next_start = stop;
while (curr != stop) {
while (next != stop) {
curr->prev->next = next;
next->next->prev = curr;
curr->next = next->next;
next->prev = curr->prev;
curr->prev = next;
next->next = curr;
next = curr->next;
}
curr = start->next;
next = curr->next;
stop = stop->prev;
}
len = 0;
li = start = next_start->prev;
}
li = li->next;
}
}
```
:::info
想試著修改 reverseK()，在函式裡面可以呼叫 reverse()
程式(以下)還有問題，待編輯
:::
```cpp
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
// Assume k is a positive integer and is less than or equal to the length of
// the linked list.
if (!head || head->prev == head->next)
return;
int len = 0;
struct list_head *li = head->next, *start = head,
*new_head = head, *new_start;
while (li != head) {
len++;
if (len == k) {
new_start = li->next;
start->next->prev = new_head;
new_start->prev->next = new_head;
new_head->next = start->next;
new_head->prev = new_start->prev;
q_reverse(new_head);
new_head->next->prev = start;
new_head->prev->next = new_start;
len = 0;
start = new_start;
li = new_start;
continue;
}
li = li->next;
}
}
```
---
### q_sort
>Sort elements of queue in ascending/descending order
目前此方法是採遞迴 top-down merge sort 來排序
正在[嘗試引用 lib/list_sort.c](#研讀-Linux-核心原始程式碼的-liblist_sort.c)
```cpp
struct list_head *merge_sort(struct list_head *head, bool descend)
{
if (!head || !head->next)
return head;
struct list_head *slow, *fast, *left, *right;
slow = fast = left = head;
// left = head->next;
while (fast && fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
right = slow->next;
slow->next = NULL;
right->prev = NULL;
left = merge_sort(left, descend);
right = merge_sort(right, descend);
struct list_head **ptr = &head;
for (;;) {
if (!left) {
*ptr = right;
break;
}
if (!right) {
*ptr = left;
break;
}
if (strcmp(list_entry(left, element_t, list)->value,
list_entry(right, element_t, list)->value) > 0) {
if (descend) {
*ptr = left;
ptr = &left->next;
left = left->next;
} else {
*ptr = right;
ptr = &right->next;
right = right->next;
}
} else {
if (descend) {
*ptr = right;
ptr = &right->next;
right = right->next;
} else {
*ptr = left;
ptr = &left->next;
left = left->next;
}
}
}
return head;
}
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || head->next == head->prev)
return;
head->prev->next = NULL;
head->next = merge_sort(head->next, descend);
// re-link prev pointer
struct list_head *li = head->next, *prev = head;
while (li) {
li->prev = prev;
li = li->next;
prev = prev->next;
}
prev->next = head;
head->prev = prev;
}
```
---
### q_ascend
>Remove every node which has a node with a strictly less value anywhere to the right side of it
```cpp
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
int count = 1;
if (!head || head->prev == head->next)
return 0;
struct list_head *curr = head->prev, *min = head->prev, *prev = curr->prev;
while (curr->prev != head) {
element_t *previous;
const element_t *min_element;
previous = list_entry(prev, element_t, list);
min_element = list_entry(min, element_t, list);
if (strcmp(previous->value, min_element->value) > 0) {
list_del(prev);
q_release_element(previous);
prev = curr->prev;
} else {
min = curr = prev;
count++;
prev = curr->prev;
}
}
return count;
}
```
---
### q_descend
>Remove every node which has a node with a strictly greater value anywhere to the right side of it
```cpp
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
int count = 1;
if (!head || head->prev == head->next)
return 0;
struct list_head *curr = head->prev, *max = head->prev, *prev = curr->prev;
while (curr->prev != head) {
element_t *previous;
const element_t *max_element;
previous = list_entry(prev, element_t, list);
max_element = list_entry(max, element_t, list);
if (strcmp(previous->value, max_element->value) < 0) {
list_del(prev);
q_release_element(previous);
prev = curr->prev;
} else {
max = curr = prev;
count++;
prev = curr->prev;
}
}
return count;
}
```
---
### q_merge
> Merge all the queues into one sorted queue, which is in ascending/descending order
`queue_contex_t` 資料結構中用來串接每個 queue 的 `chain` 一樣也是會有一個 `head` 指標當作 [dummy node (或叫 sentinel node)](https://en.wikipedia.org/wiki/Sentinel_node)
```cpp
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *context = list_entry(head->next, queue_contex_t, chain);
struct list_head *first_queue;
context->q->prev->next = NULL;
struct list_head *li = context->chain.next;
while (li != head) {
first_queue = context->q->next;
queue_contex_t *li_context = list_entry(li, queue_contex_t, chain);
li_context->q->prev->next = NULL;
struct list_head *curr = li_context->q->next;
struct list_head **ptr = &context->q->next;
for (;;) {
if (!curr) {
*ptr = first_queue;
break;
}
if (!first_queue) {
*ptr = curr;
break;
}
if (strcmp(list_entry(first_queue, element_t, list)->value,
list_entry(curr, element_t, list)->value) > 0) {
if (descend) {
*ptr = first_queue;
ptr = &first_queue->next;
first_queue = first_queue->next;
} else {
*ptr = curr;
ptr = &curr->next;
curr = curr->next;
}
} else {
if (descend) {
*ptr = curr;
ptr = &curr->next;
curr = curr->next;
} else {
*ptr = first_queue;
ptr = &first_queue->next;
first_queue = first_queue->next;
}
}
}
context->size += li_context->size;
INIT_LIST_HEAD(li_context->q);
li_context->size = 0;
li = li->next;
}
struct list_head *index = context->q, *next = index->next;
while (next) {
next->prev = index;
index = index->next;
next = index->next;
}
context->q->prev = index;
index->next = context->q;
return context->size;
}
```
---
## 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)
此方法是使用 buttom up merge sort，並且沒有使用遞迴
Sign in with Wallet
Connect another wallet