###### tags: `Linux`
# 2023q1 Homework1 (lab0)
contributed by < [`shhung`](https://github.com/shhung) >
## 開發環境
本次lab採用wsl作為linux開發環境
```bash
$ 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: 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-10210U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 12
BogoMIPS: 4224.01
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflu
sh mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc arch_per
fmon rep_good nopl xtopology cpuid pni pclmulqdq vmx 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 tpr_shadow vn
mi ept vpid ept_ad fsgsbase bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap
clflushopt xsaveopt xsavec xgetbv1 xsaves flush_l1d arch_capabilities
Virtualization features:
Virtualization: VT-x
Hypervisor vendor: Microsoft
Virtualization type: full
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
Vulnerabilities:
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknown
Retbleed: Mitigation; Enhanced IBRS
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 IBRS, IBPB conditional, RSB filling, PBRSB-eIBRS SW sequ
ence
Srbds: Unknown: Dependent on hypervisor status
Tsx async abort: Not affected
```
## 開發過程
- [x] q_new
- [x] q_free
- [x] q_insert_head
- [x] q_insert_tail
- [x] q_remove_head
- [x] q_remove_tail
- [x] q_size
- [x] q_delete_mid
- [x] q_delete_dup
- [x] q_swap
- [x] q_reverse
- [x] q_reverseK
- [ ] q_sort
- [x] q_descend
- [ ] q_merge
### `q_new`
配置記憶體位置給新的head，並使用`INIT_LIST_HEAD`來初始化
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
透過`list_for_each_entry_safe`走遍linked list，先將節點移除後再釋放記憶體
```c
void q_free(struct list_head *head)
{
if (!head)
return;
element_t *pos, *safe;
list_for_each_entry_safe (pos, safe, head, list) {
list_del(&pos->list);
q_release_element(pos);
}
free(head);
}
```
### `q_insert_head`
透過`list_add`將新的節點加在head之後
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return NULL;
int len = (strlen(s) + 1) * sizeof(char);
element_t *item = malloc(sizeof(element_t));
item->value = malloc(len);
memset(item->value, '\0', len);
strncpy(item->value, s, strlen(s));
list_add(&item->list, head);
return true;
}
```
### `q_insert_tail`
透過`list_add`將新的節點加在head之後
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return NULL;
int len = (strlen(s) + 1) * sizeof(char);
element_t *item = malloc(sizeof(element_t));
item->value = malloc(len);
memset(item->value, '\0', len);
strncpy(item->value, s, strlen(s));
list_add_tail(&item->list, head);
return true;
}
```
### `q_remove_head`
透過`list_del`將head的下一個節點移除，並將`element_t`的位置傳回
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
element_t *item = list_entry(head->next, element_t, list);
list_del(head->next);
if (!sp)
return item;
memset(sp, '\0', bufsize);
strncpy(sp, item->value, bufsize - 1);
return item;
}
```
### `q_remove_tail`
透過`list_del`將head的上一個節點移除，並將`element_t`的位置傳回
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
element_t *item = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (!sp)
return item;
memset(sp, '\0', bufsize);
strncpy(sp, item->value, bufsize - 1);
return item;
}
```
### `q_delete_mid`
透過slow和fast兩個pointer以不同的走訪速度來找到中間點
```c
bool q_delete_mid(struct list_head *head)
{
if (!head)
return NULL;
if (list_empty(head))
return NULL;
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
struct list_head *slow = head->next, *fast = head->next;
while ((fast != head) && (fast->next != head)) {
slow = slow->next;
fast = fast->next->next;
}
element_t *item = list_entry(slow, element_t, list);
list_del(slow);
q_release_element(item);
return true;
}
```
### `q_delete_dup`
取出第一個節點做起始的比較，從第二個節點開始走訪，可能遇到兩種情況
- 兩個節點的值相同
將前一個節點刪除、記錄走訪到的節點，並設定`flag`
- 兩個節點的值不同
透過`flag`的值判斷是否需要將前一個節點刪除
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
element_t *toDelete, *item;
struct list_head *pos, *safe;
int flag = 0;
toDelete = list_entry(head->next, element_t, list);
pos = head->next->next;
safe = pos->next;
while (pos != head) {
item = list_entry(pos, element_t, list);
if (!strcmp(toDelete->value, item->value)) {
list_del(&toDelete->list);
q_release_element(toDelete);
toDelete = item;
flag = 1;
} else if (flag) {
list_del(&toDelete->list);
q_release_element(toDelete);
toDelete = item;
flag = 0;
} else {
toDelete = item;
}
pos = safe;
safe = pos->next;
}
return true;
}
```
### `q_swap`
`q_swap`就是k=2時的reverseK，所以直接呼叫`q_reverseK`
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
q_reverseK(head, 2);
}
```
### `q_reverse`
逐個節點將`next`與`prev`所指的節點交換，由於只對走訪到的節點做操作，不會影響後續節點的走訪
```c
void q_reverse(struct list_head *head)
{
if (!head)
return;
if (list_empty(head))
return;
struct list_head *pos, *safe;
list_for_each_safe (pos, safe, head) {
pos->next = pos->prev;
pos->prev = safe;
}
head->next = head->prev;
head->prev = safe;
}
```
### `q_reverseK`
建立`newList`與`tmp`來完成中間操作
- newList
儲存反轉後n$\times$k個節點的list
- tmp
接收切割出的k個節點，呼叫`q_reverse`對其反轉再接到`newList`
最後將`newList`透過`list_splice`從head的開始位置插入
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head)
return;
if (list_empty(head))
return;
if (q_size(head) < k)
return;
LIST_HEAD(newList);
LIST_HEAD(tmp);
struct list_head *pos, *safe;
int cnt = 1;
list_for_each_safe (pos, safe, head) {
if (cnt == k) {
list_cut_position(&tmp, head, pos);
q_reverse(&tmp);
list_splice_tail(&tmp, &newList);
cnt = 0;
}
cnt++;
}
list_splice(&newList, head);
}
```
### `q_sort`
實作遞迴式的merge sort
透過slow, fast兩個指標找到中間節點切分成兩個list，遞迴直到list為空或是只有一個節點，最後再由`merge_two_lists`逐步合併回一個list
```c
void merge_two_lists(struct list_head *left,
struct list_head *right,
struct list_head *result)
{
element_t *left_item, *right_item;
left_item = list_first_entry(left, element_t, list);
right_item = list_first_entry(right, element_t, list);
while (!list_empty(left) && !list_empty(right)) {
if (strcmp(left_item->value, right_item->value) < 0) {
list_move_tail(&left_item->list, result);
left_item = list_first_entry(left, element_t, list);
} else {
list_move_tail(&right_item->list, result);
right_item = list_first_entry(right, element_t, list);
}
}
list_splice_tail(left, result);
list_splice_tail(right, result);
}
```
```c
void q_sort(struct list_head *head)
{
if (list_empty(head))
return;
if (list_is_singular(head))
return;
struct list_head *slow = head, *fast = head;
do {
fast = fast->next->next;
slow = slow->next;
} while (fast != head && fast->next != head);
LIST_HEAD(left);
LIST_HEAD(right);
list_splice_tail_init(head, &right);
list_cut_position(&left, &right, slow);
q_sort(&left);
q_sort(&right);
merge_two_lists(&left, &right, head);
}
```
### `q_descend`
參考leetcode討論區提到的用stack的概念來實作
參考`list_for_each_prev_safe`這個macro進行反向走訪以符合stack的特性，取反向的第一個節點作為起始的比較，遇到比其值小的節點就刪除，反之則成為新的比較值
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
element_t *item = list_entry(head->prev, element_t, list);
char *cmp = item->value;
struct list_head *pos, *safe;
// list_for_each_prev_safe(pos, safe, head)
for (pos = head->prev->prev, safe = pos->prev; pos != head;
pos = safe, safe = pos->prev) {
item = list_entry(pos, element_t, list);
if (strcmp(cmp, item->value) >= 0) {
list_del(pos);
q_release_element(item);
} else {
cmp = item->value;
}
}
return q_size(head);
}
```
Sign in with Wallet
Connect another wallet