# 2022q1 Homework1 (lab0)
contributed by <`jttony`>
## 開發環境
```bash
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.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: 12th Gen Intel(R) Core(TM) i5-12500H
CPU family: 6
Model: 154
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
Stepping: 3
BogoMIPS: 6220.80
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov p
at pse36 clflush mmx fxsr sse sse2 ht syscall nx rdtscp lm cons
tant_tsc rep_good nopl xtopology nonstop_tsc cpuid tsc_known_fr
eq pni pclmulqdq monitor ssse3 cx16 sse4_1 sse4_2 x2apic movbe
popcnt aes xsave avx rdrand hypervisor lahf_lm abm 3dnowprefetc
h fsgsbase bmi1 avx2 bmi2 invpcid rdseed clflushopt md_clear fl
ush_l1d arch_capabilities
Virtualization features:
Hypervisor vendor: KVM
Virtualization type: full
Caches (sum of all):
L1d: 48 KiB (1 instance)
L1i: 32 KiB (1 instance)
L2: 1.3 MiB (1 instance)
L3: 18 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0
Vulnerabilities:
Gather data sampling: Not affected
Itlb multihit: Not affected
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Not affected
Retbleed: Not affected
Spec store bypass: Vulnerable
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitiz
ation
Spectre v2: Mitigation; Retpolines, STIBP disabled, RSB filling, PBRSB-eIBR
S Not affected
Srbds: Not affected
Tsx async abort: Not affected
```
## 開發過程
> refer to the <`alanjian85`>, <`yanjiew1`> homework
### Linked list in linux kernel
Linked list in linux kernel is a circular linked list as below
ref ->[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
### Preview
1. All the functions below would refer to the data structure of linked list in linux kernel
2. Study the `list.h` in the lab0-c project and [The Linux Kernel API](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html) first
3. Study the [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) and the pointer in C
### `q_new()`
Create an empty queue whose next and prev pointer point to itself, return `NULL` when allocated failed
1. Linux Kernel API provides `INIT_LIST_HEAD` function with initializes the list_head to point to itself.
2. When malloc encounters an error, it returns NULL; otherwise it returns a pointer to the allocated memory [[malloc(3)]](https://man7.org/linux/man-pages/man3/malloc.3.html#top_of_page)
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free()`
Free all storage used by queue, no effect if header is `NULL`
1. Linux Kernel API provides `list_for_each_entry_safe` function, the function have properties as below
* iterate through a doubly linked list of entries
* it ensures you don't lose track of the next entry even if the current entry is removed from the list.
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list)
q_release_element(entry);
free(l);
```
### `q_insert_head()`
Insert an element in the head
1. Linux Kernel API provides `list_add` function that insert a new entry after the specified head.
2. why using `element->value = strdup(s);` instead of `element->value = s;`
* Avoid undefined behavior:
1. May have undefined bevahior if the s string gets free
* String Ownership:
1. creating a new copy of the string s on the heap memory.
2. ensures that the string's data remains valid and unchanged for the lifetime
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(s);
if (!element->value) {
free(element);
return false;
}
list_add(&element->list, head);
return true;
}
```
### `q_insert_tail()`
Insert an element in the tail
1. Linux Kernel API provides `list_add_tail` function that insert a new entry before the specified head
2. use `strdup` function would be more robust when dealing with strings in C
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element)
return false;
element->value = strdup(s);
if (!element->value) {
free(element);
return false;
}
list_add_tail(&element->list, head);
return true;
}
```
### `q_remove_head()`
Remove the element from head of queue and return the pointer to element, `NULL` if queue is `NULL` or empty.
1. Linux Kernel API provides the function as below
* `list_empty` -> tests whether a list is empty
* `list_first_entry` -> that get the first element from a list
* `list_del` -> deletes entry from list.
2. copy the removed string to *sp
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *elem = list_first_entry(head, element_t, list);
list_del(&elem->list);
if (sp) {
for (char *i = elem->value; bufsize > 1 && *i; sp++, i++, bufsize--)
*sp = *i;
*sp = '\0';
}
return elem;
}
```
### `q_remove_tail()`
Remove the element from tail of queue and return the pointer to element, `NULL` if queue is `NULL` or empty.
1. Linux Kernel API provides the function as below
* `list_empty` -> tests whether a list is empty
* `list_last_entry` -> that get the first element from a list
* `list_del` -> deletes entry from list.
2. copy the removed string to *sp
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *elem = list_last_entry(head, element_t, list);
list_del(&elem->list);
if (sp) {
for (char *i = elem->value; bufsize > 1 && *i; sp++, i++, bufsize--)
*sp = *i;
*sp = '\0';
}
return elem;
}
```
### `q_size()`
Get the size of the queue
1. Linux Kernel API provides the `list_for_each` function that iterate over a list
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int size = 0;
struct list_head *node;
list_for_each (node, head)
size++;
return size;
}
```
### `q_delete_mid()`
Delete the middle node in queue
1. Linux Kernel API provides the `list_entry` function get the struct for this entry
2. use the slow and fast pointer to calcuate the middle position
concept as below
```
init
slow
|
v
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
^
|
fast
```
```
fast move 2 step
slow move 1 step
slow
|
v
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
^
|
fast
```
```
fast move 2 step
slow move 1 step
slow
|
v
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
^
|
fast
```
```
fast move 2 step -> arrive NULL
slow pointer would not move
slow
|
v
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
^
|
fast
```
```c
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 *slow, *fast;
slow = fast = head->next;
for (; fast != head && (fast = fast->next) != head; fast = fast->next)
slow = slow->next;
element_t *elem = list_entry(slow, element_t, list);
list_del(&elem->list);
q_release_element(elem);
return true;
}
```
### `q_delete_dup()`
Delete all nodes that have duplicate string, leaving only distinct strings from the original queue.
1. refer to <`alanjian85`> algorithm
2. use the prev pointer to compare the prev node value and current node value
3. initialize a bool var `dup` in order to delete the last duplicate string
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
bool dup = false;
element_t *prev = NULL, *curr;
list_for_each_entry (curr, head, list) {
bool equal = prev && !strcmp(prev->value, curr->value);
if (equal || dup) {
list_del(&prev->list);
q_release_element(prev);
dup = equal;
}
prev = curr;
}
if (dup) {
list_del(&prev->list);
q_release_element(prev);
}
return true;
}
```
### `q_swap()`
Swap every two adjacent nodes
1. Linux Kernel API provides the `list_move` function
2. The concept would as below
```c
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head))
return;
struct list_head *node;
list_for_each(node, head) {
if (node->next == head)
break;
list_move(node, node->next);
}
}
```
### `q_reverse()`
Reverse elements in queue
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe (node, safe, head)
list_move(node, head);
}
```
### `q_reverseK()`
Given the head of a linked list, reverse the nodes of the list k at a time.
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
struct list_head *node = head->next;
for (;;) {
struct list_head *safe = node, *start = node->prev;
for (int i = 0; i < k; i++, node = node->next) {
if (node == head)
return;
}
node = safe;
safe = node->next;
for (int i = 0; i < k; i++, node = safe, safe = safe->next)
list_move(node, start);
}
}
```
### `q_sort()` / `q_mergeTwo()`
* use the recursive merge sort method to sort the linked list
* use the slow fast pointer to find the middle point and divide the linked list into two subset.
```c
void q_sort(struct list_head *head, bool descend)
{
if (!head || list_empty(head) || list_is_singular(head)) {
return; // Nothing to sort
}
struct list_head *slow = head, *fast = head->next;
for (; fast != head && fast->next != head; fast = fast->next->next)
slow = slow->next;
struct list_head left;
list_cut_position(&left, head, slow);
q_sort(&left, descend);
q_sort(head, descend);
q_merge_two(head, &left, descend);
}
static int q_merge_two(struct list_head *first, struct list_head *second, bool descend)
{
if (!first || !second)
return 0;
int size = 0;
LIST_HEAD(tmp);
while (!list_empty(first) && !list_empty(second)) {
element_t *f = list_first_entry(first, element_t, list);
element_t *s = list_first_entry(second, element_t, list);
if ((descend && strcmp(f->value, s->value) > 0) || (!descend && strcmp(f->value, s->value) <= 0))
list_move_tail(&f->list, &tmp);
else
list_move_tail(&s->list, &tmp);
size++;
}
size += q_size(first);
list_splice_tail_init(first, &tmp);
size += q_size(second);
list_splice_tail_init(second, &tmp);
list_splice(&tmp, first);
return size;
}
```
### q_ascend()
```c
int q_ascend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *entry = NULL;
int size = 0;
list_for_each_entry (entry, head, list) {
struct list_head *prev = entry->list.prev, *safe = prev->prev;
for (; prev != head; prev = safe, safe = safe->prev) {
element_t *prev_entry = list_entry(prev, element_t, list);
if (strcmp(prev_entry->value, entry->value) <= 0)
break;
size--;
list_del(prev);
q_release_element(prev_entry);
}
size++;
}
return size;
}
```
### q_descend()
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
element_t *entry = NULL;
int size = 0;
list_for_each_entry (entry, head, list) {
struct list_head *prev = entry->list.prev, *safe = prev->prev;
for (; prev != head; prev = safe, safe = safe->prev) {
element_t *prev_entry = list_entry(prev, element_t, list);
if (strcmp(prev_entry->value, entry->value) >= 0)
break;
size--;
list_del(prev);
q_release_element(prev_entry);
}
size++;
}
return size;
}
```
### q_merge()
```c
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
int queue_size = 0;
queue_contex_t *first, *second;
first = list_first_entry(head, queue_contex_t, chain),
second = list_entry(first->chain.next, queue_contex_t, chain);
while (second->q) {
queue_size = q_merge_two(first->q, second->q, descend);
second->q = NULL;
list_move_tail(&second->chain, head);
second = list_entry(first->chain.next, queue_contex_t, chain);
}
return queue_size;
}
```
Sign in with Wallet
Connect another wallet