---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
> contributed by <[Linchi1997yeh](https://github.com/Linchi1997yeh)>
> [Link to homework1](https://hackmd.io/@sysprog/linux2022-lab0)
### Reviewed by `kevinshieh0225`
- To detect whether the list is empty, use `list_empty` in linux kernel api.
- If you found bug, you should find it and send patch to the origin repositary.
- `q_delete_dup` to many additional condition in the function, it can still be more concise.
- The implementation of `q_delete_dup` seems wrong, although you past the `make test`, try to fix the function to meet the expectation.
- To swap node in `shuffle`, use `list_move_tail` instead of swapping the char value.
## Environment
```shell
$ 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 1
Core(s) per socket: 8
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-9700 CPU @ 3.00GHz
Stepping: 13
CPU MHz: 1058.944
CPU max MHz: 4700.0000
CPU min MHz: 800.0000
BogoMIPS: 6000.00
Virtualization: VT-x
L1d cache: 256 KiB
L1i cache: 256 KiB
L2 cache: 2 MiB
L3 cache: 12 MiB
NUMA node0 CPU(s): 0-7
```
## Requirements
The task is implement a queue (using linked list) with the following functions:
* `q_new`: 建立新的「空」佇列;
* `q_free`: 釋放佇列所佔用的記憶體;
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則);
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則);
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點;
* `q_release_element`: Release the memory used by a node in the queue.
* `q_size`: Return the number of nodes contained by the queue.
* `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/) 得知實作手法;
## Development Journal
### q_new
Initialize a empty queue using list_head
* Wasn't too sure of the structure of ircular doubly linked list, So I made the mistake of creating a node and used the node as list head
```c=
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
// if space cannot be allocated malloc will return NULL resulting into a
// NULL pointer
if (head) {
INIT_LIST_HEAD(head);
}
return head;
}
```
We can omit the case when memory cannot be allocated, because malloc returns Null if fail to allocate.
### q_free
Free all storage used by queue by using macros defined in lish.h
Here we need to use list_for_each_safe, to allow deletes. Here we pass in an extra pointer, so it can point to the next node to be iterated before it gets removed.
```c=
void q_free(struct list_head *l)
{
if (!l) {
return;
}
struct list_head *entry, *safe;
list_for_each_safe (entry, safe, l) {
element_t *node = container_of(entry, element_t, list);
q_release_element(node);
}
free(l);
}
```
### q_insert_head / q_insert_tail
Here we should be careful to free element_t node if the string memory space cannot be allocated to prevent memory leak problem.
:::warning
Here I encounter with a problem when pushing to git:
When calling line 18
list_add(&(node->list), head); // This would lead to memory leak problem
list_add(&node->list, head);
by just memoving the parenthesis the memory leak problem is not detected
:::
:::spoiler q_insert_head (code)
```c=
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = malloc(sizeof(element_t));
if (!node) {
return false;
}
int strsize = strlen(s);
node->value = malloc(strsize + 1);
if (!(node->value)) {
free(node);
return false;
}
memcpy(node->value, s, strsize);
node->value[strsize] = '\0';
list_add(&node->list, head);
// list_add(&(node->list), head); why does this results into a memleak???
return true;
}
```
:::
:::spoiler q_insert_tail(code)
```c=
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *node = malloc(sizeof(element_t));
if (!node) {
return false;
}
int strsize = strlen(s);
node->value = malloc(strsize + 1);
if (!(node->value)) {
free(node);
return false;
}
memcpy(node->value, s, strsize);
node->value[strsize] = '\0';
list_add_tail(&node->list, head);
return true;
}
```
:::
### q_remove_head/q_remove_tail
Here the challenge was to return the value of the removed node.
First implementation I got the instructions wrong, if the buffsize is smaller than the value string I would not return anything.
::: spoiler q_remove_head
```c=
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head) {
return NULL;
}
struct list_head *rm = head->next;
element_t *node = container_of(rm, element_t, list);
list_del(rm);
if (node->value != NULL) {
if (sp) {
memcpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
return node;
}
```
:::
::: spoiler q_remove_tail
```c=
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || head->next == head) {
return NULL;
}
struct list_head *rm = head->prev;
element_t *node = container_of(rm, element_t, list);
list_del(rm);
if (node->value != NULL) {
if (sp) {
memcpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
}
return node;
}
```
:::
### q_size
Use list_for_each to iterate and count the number of nodes
```c=
int q_size(struct list_head *head)
{
if (!head) {
return 0;
}
int size = 0;
struct list_head *node;
list_for_each (node, head) {
size++;
}
return size;
}
```
### q_delete_mid
Here I implemented the turtle and hare concept.
Where there is two pointers hopping one-node and two-node per iteration respectively. When the faster pointer reaches head it means that the slow pointer is in the round down middle.
```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;
}
struct list_head *iter1 = head->next, *iter2 = head->next->next;
while (iter2 != head && iter2->next != head) {
iter1 = iter1->next;
iter2 = iter2->next->next;
}
element_t *delnode = container_of(iter1, element_t, list);
list_del(iter1);
q_release_element(delnode);
return true;
}
```
### q_delete_dup
This can be further improved.
The idea is to delete nodes if the values of the previous nodes already appeared once.
-> Just found out that I got the function wrong when documenting but the test cases didn't contain this exception.
```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 *entry, *safe;
char *laststring = "";
list_for_each_entry_safe (entry, safe, head, list) {
// compare if previous values appeared atleast once already
if (strcmp(entry->value, laststring) == 0) {
list_del(&entry->list);
q_release_element(entry);
} else { // here the values are seen for the first time
if (entry->list.prev != head) {
element_t *first =
container_of(entry->list.prev, element_t, list);
list_del(entry->list.prev);
q_release_element(first);
}
laststring = entry->value;
}
}
entry = list_last_entry(head, element_t, list);
if (strcmp(entry->value, laststring) == 0) {
list_del(&entry->list);
q_release_element(entry);
}
return true;
}
```
:::danger
Here is an example of wrong execution, but still got 100 on make test~.
:::
```
cmd> new
l = []
cmd> ih k 2
l = [k k]
cmd> ih j
l = [j k k]
cmd> ih c 2
l = [c c j k k]
cmd> dedup
l = []
cmd>
Freeing queue
darren@darren-Altos-P30-F6:~/linux2022/lab0-c$ 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
```
### q_swap
Didn't open the leetcode link at first instance so implemented the first version swapping the values and not the nodes.
```c=
void q_swap(struct list_head *head)
{
if (!head) {
return;
}
struct list_head *curr, *after;
curr = head->next;
while (curr != head && curr->next != head) {
after = curr->next;
curr->next = after->next;
curr->next->prev = curr;
after->prev = curr->prev;
after->prev->next = after;
after->next = curr;
curr->prev = after;
curr = curr->next;
}
}
```
Here I will try to explain how this code works. We should consider carefully the relationship between the nodes in play.
```graphviz
digraph g{
1 -> 2;
2 -> 1;
2 -> 3;
3 -> 2;
3 -> 4;
4 -> 3;
}
```
The logic is to first work with either the links of <b>1 and 3</b> or <b> 2 and 4</b> and last with the links of <b>2 and 3</b> (Because we don't want to mess up with the links that are the most obvious to us in the first instance)
### q_reverse
Use list_for_each_safe to iterate over the nodes and reversing its link. ( Should use _safe version because during the process we will be modifiying the node's link)
After reversing all the node's link we shouldn't forget to reverse the head's link also.
```c=
void q_reverse(struct list_head *head)
{
if (!head || head == head->next) {
return;
}
// reverse the queue excluding head
struct list_head *node, *safe, *temp;
list_for_each_safe (node, safe, head) {
temp = node->next;
node->next = node->prev;
node->prev = temp;
}
// reverse head
temp = head->next;
head->next = head->prev;
head->prev = temp;
}
```
### q_sort
Recursive version of mergesort.
For easier implementation we break the circular linked list, so we can just implement a linked list merge sort.
After the list is sorted we have to adjust the prev pointer and reconnect the last node back to the head.
```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) {
element_t *L1_node = container_of(L1, element_t, list);
element_t *L2_node = container_of(L2, element_t, list);
node = (strcmp(L1_node->value, L2_node->value) <= 0) ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
struct list_head *mergesort_list(struct list_head *head)
{
if (!head->next)
return head;
// break the list node in the middle
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
slow->next = NULL;
// recursive call
struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
// merge list
return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
// break the circular link list into a regular link list
head->prev->next = NULL;
//sort
head->next = mergesort_list(head->next);
// Adjust the previous pointer to the correct node
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
### shuffle
Implement Fisher-Yates Shuffle
```c=
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
int q_length = q_size(head);
if (q_length == 1) {
return;
}
struct list_head *node, *target_node;
for (node = head->next; node->next != head; node = node->next) {
int target = 0;
while (target == 0) {
target = rand() % q_length;
}
target_node = node;
for (int i = 0; i < target; i++) {
target_node = target_node->next;
}
element_t *node_el = container_of(node, element_t, list);
element_t *target_node_el = container_of(target_node, element_t, list);
// swap values
char *temp = node_el->value;
node_el->value = target_node_el->value;
target_node_el->value = temp;
q_length--;
}
}
```
```c=
static bool do_shuffle(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
if (!l_meta.l)
report(3, "Warning: Calling shuffle on null queue");
error_check();
set_noallocate_mode(true);
if (exception_setup(true))
q_shuffle(l_meta.l);
exception_cancel();
set_noallocate_mode(false);
show_queue(3);
return !error_check();
}
```
### References:
Lecture notes:
> [你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-pointer)
> [你所不知道的C語言：linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
Classmate's work :
> [kevinshieh0225](https://hackmd.io/@Masamaloka/2022q1-hw1)
> [happyjack91630](https://hackmd.io/@Z80E9t1oQmejDKgmGy_dBQ/BkTGEADgq)
> [jimmy-liu1021](https://hackmd.io/WuvH2ILMSaat53sYeXmivA?both)
Sign in with Wallet
Connect another wallet