# lab0-c
contributed by < [Eric Lin](https://github.com/ericlinsechs) >
> [lab0](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-a) is a homework of the course [Linux 核心設計/實作](http://wiki.csie.ncku.edu.tw/linux/schedule) by [jserv](http://wiki.csie.ncku.edu.tw/User/jserv)
* My fork: [lab0-c](https://github.com/ericlinsechs/lab0-c)
* Original source code: [lab0-c](https://github.com/sysprog21/lab0-c)
:::info
This lab aims to assessing one's C Programming Skills. Some of the skills tested are:
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing redundant information in data structures.
* Implementing robust code that operates correctly with invalid arguments, including NULL pointers.
:::
Check [C Programming Lab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf) for more information.
## Environment
```
$ gcc --version
gcc (Ubuntu/Linaro 8.4.0-3ubuntu2) 8.4.0
$ lscpu
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
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: 0x00
Model: 0
Stepping: 0x0
BogoMIPS: 48.00
NUMA node0 CPU(s): 0-7
```
## Overview
### Structures
> Source: [cprogramminglab](https://www.cs.cmu.edu/afs/cs/academic/class/15213-s20/www/labs/cprogramminglab.pdf)
The file `queue.h` and `list.h` contains declarations of the following structures:
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
typedef struct {
char *value;
struct list_head list;
} element_t;
```
* `list_head` is a circular doubly-linked list for queue contents.
* `element_t` has fields `value` and `list`, storing a pointer to a string and a structure of queue list.
In the starter code, the queue contains only a single field of type`list_head`, but you can add other fields `list` which is intruded in `element_t`.
> In the picture above is a singly-linked list rather than a doubly-linked list in our case of implementing queue.
> Check the benefits of using [intrusive-linked-lists](https://www.data-structures-in-practice.com/intrusive-linked-lists/).
### Macro
#### offsetof
```c
#include <linux/stddef.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
```
From man page:
> The macro `offsetof()` returns the offset of the field member from the start of the structure type.
1. `(TYPE *)0`: casting the value 0 to the pointer type `Type *`. Which places a struct object at memory address zero.
2. `&((TYPE *)0)->MEMBER`: getting the address of struct field `MEMBER` of this struct object. Since the address of struct object is 0, the the address of `MEMBER` is the offset in bytes.
3. Casting the address to an `size_t` which has the same size as a pointer.
#### container_of
`container_of()` is a macro defined in `<linux/kernel.h>`.
```c
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))
```
From [kernel doc](https://www.kernel.org/doc/Documentation/driver-model/design-patterns.txt):
> What `container_of()` does is to obtain a pointer to the containing struct from a pointer to a member by a simple subtraction using the offsetof() macro from standard C, which allows something similar to object oriented behaviours.
**Notice that the contained member must not be a pointer, but an actual member for this to work.**
According to [C99 Standard](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf) in chapter **6.5.6 Additive operators**
> 7. For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.
> 8. When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression.
It is neccessary to do `(char *)` cast in this macro to ensure that pointer arithmetic operates on a byte level basis. When you subtract an offset from a pointer, you are moving the pointer backward by the number of bytes indicated by the offset. However, the actual size of the structure might be different due to padding and alignment requirements.
For this point, We can see the following example:
```c
#include <stdio.h>
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) \
((type *) ((char *) (ptr) - offsetof(type, member)))
#define wrong_container_of(ptr, type, member) \
((type *) ((ptr) - offsetof(type, member)))
struct demo {
int v1;
float v2;
};
int main()
{
struct demo s1, *s2;
float *f = &s1.v2;
printf("int: %lu, float: %lu\n", sizeof(int), sizeof(float));
printf("s1: %p\n", &s1);
s2 = container_of(f, struct demo, v2);
printf("s2: %p\n", s2);
s2 = wrong_container_of(f, struct demo, v2);
printf("s2: %p\n", s2);
return 0;
}
```
result:
```
int: 4, float: 4
s1: 0x7ffd968da760
s2: 0x7ffd968da760
s2: 0x7ffd968da754
```
In the example, when we apply the `container_of` macro, the addresses of `s1` and `s2` match. However, when `wrong_container_of` macro is applied, 16 bytes(`sizeof(float) * 4 == 16`) of offset has been conduct, the addresses of two don't match.
## Functions for Queue
### q_new
> Return NULL if a failing call to malloc().
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(struct list_head));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
```
### q_free
> Traverse elements linked to `list_head` and free each of them.
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *entry = NULL, *next = NULL;
list_for_each_entry_safe (entry, next, l, list)
q_release_element(entry);
free(l);
}
```
### q_insert_head
> `strdup` returns a pointer to a new string which is a duplicate of the string s. A terminating null byte ('\0') is also added.
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_ele = (element_t *) malloc(sizeof(element_t));
if (!new_ele)
return false;
/* Make value point to a duplicate of s */
if (!(new_ele->value = strdup(s))) {
free(new_ele);
return false;
}
list_add(&new_ele->list, head);
return true;
}
```
### q_insert_tail
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new_ele = (element_t *) malloc(sizeof(element_t));
if (!new_ele)
return false;
/* Make value point to a duplicate of s */
if (!(new_ele->value = strdup(s))) {
free(new_ele);
return false;
}
list_add_tail(&new_ele->list, head);
return true;
}
```
### q_remove_head
> Return NULL if `head` is NULL or empty.
> Get the first element in queue by `list_first_entry`
>`strncpy` copies the string pointed to by `ele->value`.
```c
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_first_entry(head, element_t, list);
list_del(&ele->list);
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
### q_remove_tail
```c
/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *ele = list_last_entry(head, element_t, list);
list_del(&ele->list);
if (sp) {
strncpy(sp, ele->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return ele;
}
```
### q_size
> Traverse each list in `head` and count them by `i`.
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
struct list_head *n = NULL;
int i = 0;
list_for_each (n, head)
i++;
return i;
}
```
### q_delete_mid
> Move the head node forward and the tail node backward untill reaching the middle node.
```c
/* Delete the middle node in queue */
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 *f = head->next;
for (struct list_head *b = head->prev; b != f && f->next != b;) {
b = b->prev;
f = f->next;
}
list_del(f);
q_release_element(list_entry(f, element_t, list));
return true;
}
```
### q_reverse
> Traverse list and swap their next and prev.
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head)) {
return;
}
struct list_head *pos = head, *tmp;
// traverse list and swap their next and prev
do {
tmp = pos->next;
pos->next = pos->prev;
pos->prev = tmp;
pos = pos->prev;
} while (pos != head);
}
```
### q_sort
> Recursive quick sort.
```c
struct list_head *merge_sort(struct list_head *start, struct list_head *end)
{
// if only one node, just return
if (start == end)
return start;
// find mid point and split into 2 parts
struct list_head *mid = start, *flag = start;
for (; flag->next && flag->next->next; flag = flag->next->next)
mid = mid->next;
flag = mid->next;
mid->next = NULL;
// keep spliting on both parts
struct list_head *left = merge_sort(start, mid);
struct list_head *right = merge_sort(flag, end);
// merge 2 splited list
struct list_head *new_head = start, **p_tmp = &new_head;
for (element_t *l, *r; left && right; p_tmp = &(*p_tmp)->next) {
l = list_entry(left, element_t, list);
r = list_entry(right, element_t, list);
struct list_head **next;
next = strcmp(l->value, r->value) < 0 ? &left : &right;
*p_tmp = *next;
*next = (*next)->next;
}
*p_tmp = left ? left : right;
return new_head;
}
```
```c
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
if (!head || head->prev == head->next)
return;
// do merge sort on list
struct list_head *start = head->next, *end = head->prev;
end->next = NULL;
// connect head and sorted list
head->next = merge_sort(start, end);
head->next->prev = head;
// repair all prev links
for (end = head; end->next; end = end->next)
end->next->prev = end;
end->next = head;
head->prev = end;
if (descend)
q_reverse(head);
}
```
### q_descend
> First convert the list to non-circular by `end->next = NULL` to creating a stop condition.
> If current value is not greater than the next value, delete the node.
> In the end, convert the list back to circular list by linking the end and the head node.
```c
static void descend(struct list_head *head);
static void descend(struct list_head *head)
{
if (!head)
return;
descend(head->next);
if (!head->next)
return;
element_t *e_cur = list_entry(head, element_t, list);
element_t *e_next = list_entry(head->next, element_t, list);
if (strcmp(e_cur->value, e_next->value) < 0) {
list_del(head);
q_release_element(e_cur);
}
return;
}
```
```c
/* Remove every node which has a node with a strictly greater value anywhere to
* the right side of it */
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head))
return 0;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
descend(head->next);
struct list_head *end = NULL;
/* Repair end next link */
for (end = head; end->next; end = end->next)
;
end->next = head;
head->prev = end;
return q_size(head);
}
```
### q_merge
> Extract each link list from queue and join them in the first queue.
> Do quick sort.
```c
/* Merge all the queues into one sorted queue, which is in ascending/descending
* order */
int q_merge(struct list_head *head, bool descend)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
struct list_head *cur = head->next, *l = NULL, *start = NULL;
while ((uintptr_t) cur != (uintptr_t) head) {
queue_contex_t *ctx = list_entry(cur, queue_contex_t, chain);
l = ctx->q;
cur = cur->next;
if (!start)
start = l;
else
list_splice_tail_init(l, start);
}
q_sort(start, descend);
return q_size(start);
}
```
Sign in with Wallet
Connect another wallet