# 2022q1 Homework1 (lab0)
contributed by < [Nomad1230](https://github.com/Nomad1230) >
## 實驗環境
```
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
$ 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): 1
On-line CPU(s) list: 0
Vendor ID： GenuineIntel
Model name: Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz
CPU family： 6
Model： 158
Thread(s) per core： 1
Core(s) per socket： 1
Socket(s): 1
Stepping： 10
BogoMIPS: 4608.00
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mc
a cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall n
x rdtscp lm constant_tsc rep_good nopl xtopology nonsto
p_tsc cpuid tsc_known_freq pni pclmulqdq monitor ssse3
cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt aes xsave a
vx rdrand hypervisor lahf_lm abm 3dnowprefetch invpcid_
single pti fsgsbase avx2 invpcid rdseed clflushopt md_c
lear flush_l1d
Virtualization features:
Hypervisor 供應商： KVM
虛擬型態： 全部
Caches (sum of all):
L1d: 32 KiB (1 instance)
L1i: 32 KiB (1 instance)
L2: 256 KiB (1 instance)
L3: 8 MiB (1 instance)
NUMA:
NUMA 節點： 1
NUMA node0 CPU(s)： 0
Vulnerabilities:
Itlb multihit: KVM: Mitigation: VMX unsupported
L1tf: Mitigation; PTE Inversion
Mds: Mitigation; Clear CPU buffers; SMT Host state unknown
Meltdown: Mitigation; PTI
Spec store bypass: Vulnerable
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer
sanitization
Spectre v2: Mitigation; Full generic retpoline, STIBP disabled, RSB
filling
Srbds: Unknown: Dependent on hypervisor status
Tsx async abort: Not affected
```
## 作業要求
> [lab0](https://hackmd.io/@sysprog/linux2022-lab0)
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* q_new: 建立新的「空」佇列;
* q_free: 釋放佇列所佔用的記憶體;
* q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* q_release_element: 釋放特定節點的記憶體空間;
* q_size: 計算目前佇列的節點總量;
* q_delete_mid: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
* q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)
* q_swap: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)
* q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點;
* q_sort: 以遞增順序來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法;
## 開發過程
### q_new
:::spoiler 程式碼
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
// check if malloc success
if (!new)
return NULL;
else {
INIT_LIST_HEAD(new);
return new;
}
}
```
:::
---
### q_free
:::spoiler 程式碼
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, l) {
list_del_init(node);
q_release_element(list_entry(node, element_t, list));
}
free(l);
}
```
:::
---
### q_insert_head
:::spoiler 程式碼
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
else {
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
} else {
list_add(&new->list, head);
return true;
}
}
}
```
:::
---
### q_insert_tail
:::spoiler 程式碼
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head || !s)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
else {
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
} else {
list_add_tail(&new->list, head);
return true;
}
}
}
```
:::
---
### q_remove_head
:::spoiler 程式碼
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
else {
struct list_head *del = head->next;
list_del_init(head->next);
element_t *del_ele = list_entry(del, element_t, list);
if (sp) {
strncpy(sp, del_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return del_ele;
}
}
```
:::
---
### q_remove_tail
:::spoiler 程式碼
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head)
return NULL;
else {
struct list_head *del = head->prev;
list_del_init(head->prev);
element_t *del_ele = list_entry(del, element_t, list);
if (sp) {
strncpy(sp, del_ele->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
return del_ele;
}
}
```
:::
---
### q_size
:::spoiler 程式碼
```c
int q_size(struct list_head *head)
{
if (!head || head->next == head)
return 0;
int count = 0;
struct list_head *node;
list_for_each (node, head) {
count++;
}
return count;
}
```
:::
---
### q_delete_mid
:::spoiler 程式碼
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head || head->next == head)
return false;
element_t *del;
struct list_head **indir = &head;
struct list_head *temp = head->prev;
temp->next = NULL;
for (struct list_head *fast = head; fast && fast->next;
fast = fast->next->next)
indir = &(*indir)->next;
temp->next = head;
del = list_entry(*indir, element_t, list);
list_del_init(*indir);
q_release_element(del);
return true;
}
```
:::
---
### q_delete_dup
:::spoiler 程式碼
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
element_t *node, *safe;
list_for_each_entry_safe (node, safe, head, list) {
// if &safe->list == head, safe->value will dereference a null pointer
if (&safe->list != head) {
if (node->value && safe->value) {
if (!strcmp(node->value, safe->value)) {
list_del(&node->list);
q_release_element(node);
}
}
}
}
return true;
}
```
:::
---
### q_swap
:::spoiler 程式碼
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || head->next == head || head->next->next == head)
return;
for (struct list_head *node1 = head->next, *node2 = head->next->next;
node1 != head && node2 != head;
node1 = node1->next, node2 = node1->next) {
node1->prev->next = node2;
node2->prev = node1->prev;
node1->prev = node2;
node1->next = node2->next;
node2->next->prev = node1;
node2->next = node1;
}
}
```
:::
---
### q_reverse
原理是將每一個 list_head 中的 prev 跟 next 互相交換，當每一個 node 的 prev 跟 next 都交換完成，即可達成整個 list 的 reverse 。
先把 Linked list 中首尾相接的兩條指標設成NULL，讓 while 迴圈操作時可以順利中止並避免出錯，當最後一個 node 交換完成之後跳出迴圈，並把剛才移除的指標重新連結上。
:::spoiler
```c
void q_reverse(struct list_head *head)
{
if (!head || head->next == head)
return;
struct list_head *node = head, *temp;
head->prev->next = NULL;
head->prev = NULL;
while (1) {
temp = node->next;
node->next = node->prev;
node->prev = temp;
if (!node->prev)
break;
else
node = node->prev;
}
node->prev = head;
head->next = node;
}
```
:::
---
### q_sort
:::spoiler 程式碼
```c
void q_sort(struct list_head *head)
{
if (!head || head->next == head || head->next->next == head)
return;
int top = 0;
int listsSize = 0;
struct list_head *stack[10000] = {NULL};
struct list_head *lists[100000] = {NULL};
stack[top] = head->next;
head->prev->next = NULL;
INIT_LIST_HEAD(head);
// divide to single node
while (top >= 0) {
struct list_head *left = stack[top--];
if (left) {
struct list_head *slow = left;
struct list_head *fast;
for (fast = left->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
struct list_head *right = slow->next;
slow->next = NULL;
stack[++top] = left;
stack[++top] = right;
} else {
stack[top]->prev = stack[top];
stack[top]->next = NULL;
lists[listsSize++] = stack[top--];
}
}
// merge K sorted lists
while (listsSize > 1) {
for (int i = 0, j = listsSize - 1; i < j; i++, j--)
lists[i] = mergeTwoLists(lists[i], lists[j]);
listsSize = (listsSize + 1) / 2;
}
struct list_head *node = lists[0];
while (node->next) {
node->next->prev = node;
node = node->next;
}
node->next = head;
head->next = lists[0];
lists[0]->prev = head;
head->prev = node;
}
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0) ? &L1: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
if (!L1) {
*ptr = L2;
return head;
}
if (!L2) {
*ptr = L1;
return head;
}
return head;
}
```
:::
:::spoiler
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (strcmp(list_entry(L1, element_t, list)->value,
list_entry(L2, element_t, list)->value) < 0)
? &L1
: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((u_int64_t) L1 | (u_int64_t) L2);
return head;
}
static struct list_head *mergesort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
}
slow->prev->next = NULL;
struct list_head *left = mergesort(head);
struct list_head *right = mergesort(slow);
return mergeTwoLists(left, right);
}
/*
* Sort elements of queue in ascending order
* No effect if q is NULL or empty. In addition, if q has only one
* element, do nothing.
*/
void q_sort(struct list_head *head)
{
if (!head || head->next == head || head->next->next == head)
return;
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head *node = head->next;
node->prev = head;
while (node->next) {
node->next->prev = node;
node = node->next;
}
node->next = head;
head->prev = node;
}
```
:::
Sign in with Wallet
Connect another wallet