---
tags: linux kernel
---
# 2022q1 Homework1 (lab0)
contributed by < `huang-me` >
:::danger
注意作業書寫規範！
:notes: jserv
:::
# Prerequisites
```shell
$ sudo apt install build-essential git clang-format aspell colordiff valgrind
```
### Build cppcheck
Download cppcheck source code from [GitHub](https://github.com/danmar/cppcheck/releases).
```shell
# unzip file
tar -xf <cppcheck-version.tar.gz>
cd cppcheck-<version>
# build file and install
sudo make CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin/ -j4
sudo make install CFGDIR=/usr/share/cppcheck/ FILESDIR=/usr/bin -j4
```
# Environment
:::danger
Your gcc was too old. Upgrade your Linux distribution as soon as possible, otherwise you will encounter some unexpected issues later.
:notes: jserv
:::
```shell
$ gcc --version
gcc (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 142
Model name: Intel(R) Core(TM) i7-8550U CPU @ 1.80GHz
Stepping: 10
CPU MHz: 899.969
CPU max MHz: 4000.0000
CPU min MHz: 400.0000
BogoMIPS: 3999.93
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 8192K
NUMA node0 CPU(s): 0-7
```
# Development
## queue_new
- Use `malloc` to acquire memory space, return NULL if no space available.
Initialize list_head with `INTI_LIST_HEAD` defined in `list.h`
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(*head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
## queue_free
- Delete first node until list have no element, and delete list_head.
```c
void q_free(struct list_head *l)
{
if (!l)
return;
while (!list_empty(l)) {
element_t *node = list_first_entry(l, element_t, list);
q_remove_head(l, NULL, 0);
free(node->value);
free(node);
}
free(l);
}
```
- Use `list_for_each_entry_safe` defined in `list.h` to iterate through all nodes in list, remove them from list and release the memory.
```c
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *e, *s;
list_for_each_entry_safe (e, s, l, list) {
list_del(&(e->list));
q_release_element(e);
}
free(l);
}
```
## q_insert_head
- Use `malloc` allocate memory, `return false` if no memory can be allocated.
Use `memset` initialize the value of `newNode` and copy input to `newNode->value`
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *newNode = malloc(sizeof(element_t));
if (!newNode)
return false;
newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
if(!newNode->value) {
q_release_element(newNode);
return false;
}
memset(newNode->value, '\0', strlen(s) + 1);
strncpy(newNode->value, s, strlen(s));
list_add(&newNode->list, head);
return true;
}
```
## q_insert_tail
- Most operations are same as `q_insert_head`, the only difference is replace `list_add` with `list_add_tail`.
```c
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *newNode = malloc(sizeof(element_t));
if (!newNode)
return false;
newNode->value = malloc(sizeof(char) * (strlen(s) + 1));
if (!newNode->value) {
q_release_element(newNode);
return false;
}
memset(newNode->value, '\0', strlen(s) + 1);
strncpy(newNode->value, s, strlen(s));
list_add_tail(&newNode->list, head);
return true;
}
```
## q_remove_head
- Use `list_entry` to get the address of the entry.
Copy the entry value to sp if sp is given.
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_entry(head->next, element_t, list);
if (sp && node->value) {
strncpy(sp, node->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del(head->next);
return node;
}
```
## q_remove_tail
- Most operations are same as `q_remove_head`, the only difference is the node position is changed from `head->next` to `head->prev`.
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *node = list_entry(head->prev, element_t, list);
if (sp && node->value) {
strncpy(sp, node->value, bufsize - 1);
*(sp + bufsize - 1) = '\0';
}
list_del(head->prev);
return node;
}
```
## q_release_element
- Release the memory of `e->value` and `e` if they were defined.
```c
void q_release_element(element_t *e)
{
if (!e)
return;
if (e->value)
free(e->value);
free(e);
}
```
## q_size
- Iterate through the queue with `list_for_each` and count the number of elements.
```c
int q_size(struct list_head *head)
{
if (!head)
return -1;
int cnt = 0;
struct list_head *e;
list_for_each (e, head)
cnt++;
return cnt;
}
```
## q_delete_mid
- Use `fast/slow` pointer find middle element of linked list and delete it.
```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 *fast, *slow;
fast = slow = head->next;
while (slow->next != head && slow->next->next != head) {
slow = slow->next->next;
fast = fast->next;
}
element_t *e = list_entry(fast, element_t, list);
list_del(fast);
q_release_element(e);
return true;
}
```
## q_delete_dup
- Iterate through all list nodes, delete the node if value is same as last node.
```c
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;
element_t *e, *s;
char *last = NULL;
list_for_each_entry_safe (e, s, head, list) {
if (last && strcmp(last, e->value) == 0) {
list_del(&e->list);
q_release_element(e);
} else {
last = strdup(e->value);
}
}
return true;
}
```
:::success
`strdup` may lead to memory leak since the space is never released.
Rewrite `q_delete_dup` as following code to prevent copying data.
```c
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;
element_t *e, *s;
char *last = NULL;
list_for_each_entry_safe (e, s, head, list) {
if (last && strcmp(last, e->value) == 0) {
list_del(&e->list);
q_release_element(e);
} else {
last = e->value;
}
}
return true;
}
```
:::
## q_swap
- Reassign all pointers between list nodes.
```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 *e = head->next;
while (e != head && e->next != head) {
struct list_head *n;
n = e->next;
n->next->prev = e;
e->next = n->next;
n->next = e;
n->prev = e->prev;
e->prev->next = n;
e->prev = n;
e = e->next;
}
}
```
:::success
Shorten code with use of list.h functions.
```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 *e = head->next;
while (e != head && e->next != head) {
struct list_head *n = e->next;
list_del(n);
list_add(n, e->prev);
e = e->next;
}
}
```
:::
## q_reverse
- Exchange all node's `next` and `prev` pointer to achieve reverse.
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *e, *s;
list_for_each_safe (e, s, head) {
e->next = e->prev;
e->prev = s;
}
struct list_head *tmp = head->next;
head->next = head->prev;
head->prev = tmp;
}
```
## q_sort
- Split list into two subqueues, sort them separately and Merge into one queue.
Time complexity: `O(nlogn)`
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *fast, *slow;
fast = slow = head->next;
while (fast != head && fast->next != head) {
fast = fast->next->next;
slow = slow->next;
}
if (fast == head)
fast = fast->prev;
struct list_head *mid;
mid = slow->prev;
head->prev = mid;
mid->next = head;
q_sort(head);
struct list_head *front, *last; // ptr for 1st subqueue
front = head->next;
last = head->prev;
head->next = slow;
slow->prev = head;
head->prev = fast;
q_sort(head);
struct list_head *fr; // ptr for 2nd subqueue
fr = head->next;
last->next = fr;
fr->prev = last;
head->next = front;
front->prev = head;
// merge two subqueue
struct list_head *p1 = front, *p2 = last->next;
while (p1 != last->next && p2 != head) {
char *v1 = list_entry(p1, element_t, list)->value,
*v2 = list_entry(p2, element_t, list)->value;
if (strcmp(v1, v2) <= 0) {
p1 = p1->next;
} else {
struct list_head *tmp = p2->next;
list_del(p2);
p2->next = p1;
p2->prev = p1->prev;
p1->prev = p2;
p2->prev->next = p2;
p2 = tmp;
}
}
}
```
:::success
Shorten merge code with use of list.h function.
```c
struct list_head *p1 = front, *p2 = last->next;
while (p1 != last->next && p2 != head) {
char *v1 = list_entry(p1, element_t, list)->value,
*v2 = list_entry(p2, element_t, list)->value;
if (strcmp(v1, v2) <= 0) {
p1 = p1->next;
} else {
struct list_head *tmp = p2->next;
list_del(p2);
list_add(p2, p1->prev);
p2 = tmp;
}
}
```
:::
# Result
```shell
make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, and sort
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
:::danger
Insert/Remove time complexity test doesn't always pass in GitHub CI.
> You should read the paper and recognize the root cause.
> :notes: jserv
:::
# Fisher-Yates shuffle
- Add `q_shuffle` into `queue.c`
- Fisher-Yates shuffle steps
1. Randomly choose a node and move it to tail of the queue.
2. Repeat step 1 for `q_size` times
```c
void q_shuffle(struct list_head *head) {
if(!head || list_empty(head))
return;
struct list_head *node;
for(int cnt=q_size(head); cnt>0; cnt--) {
int x = rand() % cnt;
node = head->next;
for(int i=0; i<x; i++)
node = node->next;
list_del(node);
list_add_tail(node, head);
}
return;
}
```
- Add `q_shuffle` definition into queue.h header file.
```c
void q_shuffle(struct list_head *head);
```
- Add `do_shuffle` in `qtest.c`.
```c
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
q_shuffle(l_meta.l);
show_queue(3);
return !error_check();
}
```
- Add command shuffle to console
```c
ADD_COMMAND(shuffle, " | Shuffle the queue");
```
Sign in with Wallet
Connect another wallet