---
tags: Linux Kernal
---
# 2023q1 Homework1 (lab0)
contributed by < [POCHUN-CHEN](https://github.com/POCHUN-CHEN?tab=repositories) >
## Helpful Git skill
I have created a note to document how to use Git.
[Git基本功能教學](https://hackmd.io/bDqmgVAyS9iqDXxu5rncMw?both)
## why we should use "pointer to pointer" (indirect pointer)
This can **avoid using an additional conditional statement** at the **beginning of the data**.
:::spoiler Worse & better code comparision
* Worse code
```c
void remove_list_node(List *list, Node *target)
{
Node *prev = NULL;
Node *current = list->head;
// Walk the list
while (current != target) {
prev = current;
current = current->next;
}
// Remove the target by updating the head or the previous node.
if (!prev)
list->head = target->next;
else
prev->next = target->next;
}
```
* Better code
```c
void remove_list_node(List *list, Node *target)
{
// The "indirect" pointer points to the *address*
// of the thing we'll update.
Node **indirect = &list->head;
// Walk the list, looking for the thing that
// points to the node we want to remove.
while (*indirect != target)
indirect = &(*indirect)->next;
*indirect = target->next;
}
```
:::
### Discussing
In the program I wrote for the first time, I used this code ```*indirect = (*indirect)->next;```. I think this can reduce the use of pointer once and make the program more fast.
Q: why can't we replace
```indirect = &(*indirect)->next;``` in line 9 by
```*indirect = (*indirect)->next;```?
A: ```head``` will be changed!
See the below flow diagram:
:::spoiler Wrong way
Wrong way: ```*indirect = (*indirect)->next;```
```graphviz
digraph list{
rankdir=LR;
node [shape=record,style=normal];
head [label = "{<left>head}"];
subgraph cluster_0 {
node [shape=record];
value1 [label="{value}"];
next1 [label="{<right>next}"];
label=Node1;
}
subgraph cluster_1 {
node [shape=record];
value2 [label="{value}"];
next2 [label="{<right>next}"];
label=Node2;
}
subgraph cluster_2 {
node [shape=record,style=bold];
indir [label = "{indir}"];
label="Pointer to pointer";
}
node [shape=none]
none1 [label = ""];
edge[weight=2];
head:right:e -> next2;
next1:right:e -> next2;
next2:right:e -> none1;
edge[weight=1];
indir -> head;
}
```
:::
:::spoiler Correct way
Correct way: `indirect = &(*indirect)->next;`
```graphviz
digraph list{
rankdir=LR;
node [shape=record,style=normal];
head [label = "{<left>head}"];
subgraph cluster_0 {
node [shape=record];
value1 [label="{value}"];
next1 [label="{<right>next}"];
label=Node1;
}
subgraph cluster_1 {
node [shape=record];
value2 [label="{value}"];
next2 [label="{<right>next}"];
label=Node2;
}
subgraph cluster_2 {
node [shape=record,style=bold];
indir [label = "{indir}"];
label="Pointer to pointer";
}
node [shape=none]
none1 [label = ""];
edge[weight=2];
head:right:e -> next1;
next1:right:e -> next2;
next2:right:e -> none1;
edge[weight=1];
indir -> next1;
}
```
:::
## List structure for linked list
This is the structure diagram that I initially thought of when I first tried to understand the linked list structure.
Below diagram is an example of a singly linked list.
```graphviz
digraph list{
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
addr0 [label="{Address of List head}"];
next0 [label="{next}"];
label=List_of_head;
}
subgraph cluster_1 {
node [shape=record];
value1 [label="{value}"];
subgraph cluster_11 {
node [shape=record];
addr1 [label="{Address of List 1}"];
next1 [label="{next}"];
label=List_of_Node1;
}
label=Node1;
}
subgraph cluster_2 {
node [shape=record];
value2 [label="{value}"];
subgraph cluster_22 {
node [shape=record];
addr2 [label="{Address of List 2}"];
next2 [label="{next}"];
label=List_of_Node2;
}
label=Node2;
}
node [shape=none]
none1 [label = ""];
edge[weight=2];
indirect:right:e -> list;
list:right:e -> addr0;
target:right:e -> addr2;
next0:right:e -> addr1;
next1:right:e -> addr2;
next2:right:e -> none1;
edge [style="dashed"];
addr0:right:e -> next0;
addr1:right:e -> next1;
addr2:right:e -> next2;
edge[weight=1];
}
```
:::info
I have a question, why can't we put a `Node_head` structure in the first `List_of_head` ? As shown in the following figure.
```graphviz
digraph list{
rankdir=LR;
subgraph cluster_0 {
node [shape=record];
value0 [label="{value}"];
subgraph cluster_00 {
node [shape=record];
addr0 [label="{Address of List head}"];
next0 [label="{next}"];
label=List_of_head;
}
label=Node_head;
}
subgraph cluster_1 {
node [shape=record];
value1 [label="{value}"];
subgraph cluster_11 {
node [shape=record];
addr1 [label="{Address of List 1}"];
next1 [label="{next}"];
label=List_of_Node1;
}
label=Node1;
}
subgraph cluster_2 {
node [shape=record];
value2 [label="{value}"];
subgraph cluster_22 {
node [shape=record];
addr2 [label="{Address of List 2}"];
next2 [label="{next}"];
label=List_of_Node2;
}
label=Node2;
}
node [shape=none]
none1 [label = ""];
edge[weight=2];
indirect:right:e -> list;
list:right:e -> addr0;
target:right:e -> addr2;
next0:right:e -> addr1;
next1:right:e -> addr2;
next2:right:e -> none1;
edge [style="dashed"];
addr0:right:e -> next0;
addr1:right:e -> next1;
addr2:right:e -> next2;
edge[weight=1];
}
```
This allows for more efficient use of the `Node_head` for memory space.
Anwser: [自 Head 開始，鏈結 list 各節點，個別節點皆嵌入 list_head 結構體，不過 Head 是個特例，無法藉由 container_of 巨集來找到對應的節點，因為後者並未嵌入到任何結構體之中，其存在是為了找到 list 整體。](https://hackmd.io/@sysprog/c-linked-list#Linked-list-在-Linux-核心原始程式碼)
:::
## Linked list `container_of` structure
* List structure
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
* Element structure with char value
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
##### Note:
`typedef` define a type `struct{...}` to a new name `element_t`.
#### Flow chart:
##### Notes:
* `Head` is a special case without Node. It just use to serch for the list.
* In `element_t` structure, we can know the `value` address through counting the type size to get it. This is why we should use "container_of".
#### References:
1. [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
2. [linux/include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
## Instructions of functions in "queue.c"
:::danger
Write in English more proficiently!
:notes: jserv
:::
Homework Request:
- [X] [q_new] Create an empty queue
- [x] [q_free] Free all storage used by queue
- [x] [q_insert_head] Insert an element at head of queue
- [x] [q_insert_tail] Insert an element at tail of queue
- [x] [q_remove_head] Remove an element from head of queue
- [x] [q_remove_tail] Remove an element from tail of queue
- [x] [q_size] Return number of elements in queue
- [X] [q_delete_mid] Delete the middle node in queue
- [ ] [q_delete_dup] Delete all nodes that have duplicate string
- [X] [q_swap] Swap every two adjacent nodes
- [x] [q_reverse] Reverse elements in queue
- [x] [q_reverseK] Reverse the nodes of the list k at a time
- [x] [q_sort] Sort elements of queue in ascending order
- [ ] [q_descend] Remove every node which has a node with a strictly greater value anywhere to the right side of it
- [ ] [q_merge] Merge all the queues into one sorted queue, which is in ascending order
### [q_new] Create an empty queue
Use `INIT_LIST_HEAD`in library`list.h` to initialize `prev` & `next`.
#### Instructions:
1. Use `malloc(sizeof())`to allocate memory`new`, and check the allocated memory `new` action is succesful or not.
2. If this condition is right, use `INIT_LIST_HEAD`to initialize the `struct list_head` and return `new`.
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
4. If this condition is wrong , return Null.
:::spoiler Source Code
```c
/* Create an empty queue */
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struc list_head));
if(new){
INIT_LIST_HEAD(new);
return new;
}
return NULL;
}
```
:::
### [q_free] Free all storage used by queue
#### Instructions:
1. Check `l` exist.
2. Declare `node` to run through whole list.
3. Use `list_del` to pick up each `del` and use `q_release_element` to delete it.
:::spoiler Source Code (Version 1: Dereferenced a NULL or invalid pointerAborted)
```c
/* Free all storage used by queue */
void q_free(struct list_head *l) {
if (!l)
return;
struct list_head *curr = l->next;
while (curr != l)
{
element_t *del = list_entry(curr, element_t, list);
if (!del)
return;
list_del(&del->list);
free(del);
curr = curr->next;
}
free(l);
}
```
:::
:::spoiler Source Code (Version 2: Dereferenced a NULL or invalid pointerAborted)
```c
/* Free all storage used by queue */
void q_free(struct list_head *l) {
if (!l)
return;
struct list_head *curr = l->next;
while (curr != l)
{
element_t *del = list_entry(curr, element_t, list);
if (!del)
return;
list_del(&del->list);
q_release_element(del);
curr = curr->next;
}
free(l);
}
```
:::
:::danger
Debug:
1. Use function `q_release_element()`, instead of `free()`. Because there are not `element` just has itself, there are `value`.
2. We didn't need to check `element_t *del` is exist. It must exist when we allocate memeory before.
```c
static inline void q_release_element(element_t *e)
{
test_free(e->value);
test_free(e);
}
```
3. `curr = curr->next;` must before `list_del(&del->list)` & `q_release_element(del)`, or `curr` will pointer a cutted list node `del`. It will pointer NULL, after we delete `del`.
:::
:::spoiler Source Code (Version 3)
```c
/* Free all storage used by queue */
void q_free(struct list_head *l) {
if (!l)
return;
struct list_head *curr = l->next;
while (curr != l) {
element_t *del = list_entry(curr, element_t, list);
// if (!del)
// return;
curr = curr->next;
list_del(&del->list);
// free(del);
q_release_element(del);
}
free(l);
}
```
:::
### [q_insert_head] Insert an element at head of queue
Use `list_add`in library`list.h` to add a node next to head.
```mermaid
graph LR;
head-->node-->next;
head-.->next;
next-->node-->head;
```
```c
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
```
#### Instructions:
1. Use `malloc(sizeof())`to allocate memory`new`, and check the allocated memory `new` action is succesful or not.
2. Allocate memory to `new->value` in element_t.
3. Copy value from `s` to `new->value`
4. Use `list_add()` to add a node next to head.
Debug:
* If we want to storage 'l' long string, we need to use 'l+1' char to storage and put '\0' after each string.
* ```strncpy(new->value, s, strlen(s));``` we don't need to add one char memory size in the third input.
:::spoiler Source Code
```c
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
int sl = strlen(s);
new->value = malloc(
(sl + 1) *
sizeof(char)); // notice there are (strlen(s)+1) size need to allocate.
if (!new->value) {
free(new);
return false;
}
strncpy(new->value, s, sl);
*(new->value + sl) = '\0'; // add '\0' after string.
list_add(&new->list, head);
return true;
}
```
:::
### [q_insert_tail] Insert an element at tail of queue
This function is similar to `q_insert_head`.
The only different part is `list_add(&new->list,head)` and `list_add_tail(&new->list, head)`.
::: danger
!!Segmentation fault occurred. You dereferenced a NULL or invalid pointer!!
Sol:
We need to check, if memory is fail allocation, free fail allocation memory.
```c
if (!new->value) {
free(new);
return false;
}
```
:::
:::spoiler Source Code
```c
/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
int sl = strlen(s);
new->value = malloc(
(sl + 1) *
sizeof(char)); // notice there are (strlen(s)+1) size need to allocate.
if (!new->value) {
free(new);
return false;
}
strncpy(new->value, s, sl);
*(new->value + sl) = '\0'; // add '\0' after string.
list_add_tail(&new->list, head);
return true;
}
```
:::
### [q_remove_head] Remove an element from head of queue
```c
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
We need to check `head` is exist and not empty.
```c
/* list_empty() - Check if list head has no nodes attached */
static inline int list_empty(const struct list_head *head)
{
return (head->next == head);
}
```
```c
/**
* list_entry() - Get the entry for this node
* @node: pointer to list node
* @type: type of the entry containing the list node
* @member: name of the list_head member variable in struct @type
*
* Return: @type pointer of entry containing node
*/
#define list_entry(node, type, member) container_of(node, type, member)
```
#### Instructions:
* bufsize-1
:::warning
*(removed->value + bufsize-1) = '\0';
:::
:::danger
Debug:
*(sp + bufsize-1) = '\0';
:::
`removed->value` just exist in function `q_remove_head`. This is not helpful for modifying parameters.
:::spoiler Source Code (version 1)
```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 *removed = list_entry(head->next, element_t, list);
if (!removed)
return NULL;
list_del(&removed->list);
if (bufsize) {
strncpy(sp, removed->value, bufsize - 1);
}
*(removed->value + bufsize - 1) = '\0';
return removed;
}
```
:::
:::spoiler Source Code (version 2)
```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 *removed = list_entry(head->next, element_t, list);
if (!removed)
return NULL;
list_del(&removed->list);
if (bufsize) {
strncpy(sp, removed->value, bufsize - 1);
}
*(sp + bufsize - 1) = '\0';
return removed;
}
```
:::
### [q_remove_tail] Remove an element from tail of queue
#### Instructions:
:::spoiler Source Code (Version 1)
```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 *removed = list_entry(head->prev, element_t, list);
if (!removed)
return NULL;
list_del(&removed->list);
if (bufsize) {
strncpy(sp, removed->value, bufsize - 1);
}
*(removed->value + bufsize - 1) = '\0';
return removed;
}
```
:::
:::spoiler Source Code (Version 2)
```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 *removed = list_entry(head->prev, element_t, list);
if (!removed)
return NULL;
list_del(&removed->list);
if (bufsize) {
strncpy(sp, removed->value, bufsize - 1);
}
*(sp + bufsize - 1) = '\0';
return removed;
}
```
:::
### [q_size] Return number of elements in queue
```c
/* list_for_each - Iterate over list nodes*/
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
#### Instructions:
1. Check `head` is exist
2. Structure a `node`
3. Declarate `size = 0`, and iterate plus it by `list_for_each`
Discussing:
Why can't we use `queue_contex_t *entry` to get q_size?
```c
queue_contex_t *entry = list_entry(head, queue_contex_t, q);
return entry->size;
```
:::spoiler Source Code
```c
/* Return number of elements in queue */
int q_size(struct list_head *head)
{
if (!head)
return 0;
struct list_head *node;
int size = 0;
list_for_each (node, head)
size++;
return size;
}
```
:::
### [q_delete_mid] Delete the middle node in queue
#### Instructions:
1. Check there are not just a `head`
2. Construct two `list_head`，`rabbit`、`turtle`。
3. Check `rabbit->next`、`rabbit->next->next` is not `head`
4. Move `rabbit` two steps， and `turtle` one steps. It decides when `rabbit` arrived `head`, `turtle` will stand in the middle of list.
5. Use `list_del（turtle）` to delete `turtle`.
#### Discussing:
If list monents is odd, there is a middle node from 1.
If list monents is even, there is a middle node from 0.
e.g.
* n = 6
(6+1)/2=3.5 -> 4
* n = 5
(5+1)/2=3 -> 3
>The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing.
:::spoiler Source Code (Version 1)
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/de lete-the-middle-node-of-a-linked-list/
if (!head->next)
return false;
struct list_head *rabbit = head->next, *turtle = head->next;
while (rabbit->next != head && rabbit->next->next != head) {
rabbit = rabbit->next->next;
turtle = turtle->next;
}
turtle = turtle->next;
list_del(turtle);
return true;
}
```
:::
Update imformation is contributed by < [Risheng1128](https://github.com/Risheng1128) >
```c
while (rabbit != head && rabbit->next != head)
```
:::spoiler Source Code
```c
/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/de lete-the-middle-node-of-a-linked-list/
if (!head->next)
return false;
struct list_head *rabbit = head->next, *turtle = head->next;
while (rabbit != head && rabbit->next != head) {
rabbit = rabbit->next->next;
turtle = turtle->next;
}
list_del(turtle);
return true;
}
```
:::
### [q_delete_dup] Delete all nodes that have duplicate string
:::spoiler Source Code
```c
/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
return true;
}
```
:::
### [q_swap] Swap every two adjacent nodes
#### Instructions:
1. Check `head` exist.
2. Declare `list_head` structure `curr`, `first`, `second`. `curr` will make the list move next two steps each generation. `first` and `second` will chanege each other.
:::spoiler Source Code (Version 1: Ifinity loop)
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *curr = head->next, *first = NULL, *second = NULL;
while (curr != head && curr->next != head) {
first = curr;
second = first->next;
first->next = second->next;
first->prev = second;
second->next = first;
second->prev =curr->prev;
curr = curr->next->next;
}
}
```
:::
:::spoiler Source Code (Version 2: Ifinity loop)
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *first = head->next;
while (first != head && first->next != head) {
struct list_head *second = first->next;
first->next = second->next;
second->prev =first->prev;
first->prev->next = second;
second->next->prev = first;
first->prev = second;
second->next = first;
first = first->next;
}
```
:::
:::danger
Debug:
I didn't change the pointers `first->prev->next` & `second->next->prev`.
:::
:::spoiler Source Code (Version 3)
```c
/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head)
return;
struct list_head *first = head->next;
while (first != head && first->next != head) {
struct list_head *second = first->next;
list_del_init(first);
list_add(first, second);
first = first->next;
}
```
:::
Better code thinking.
Reference guide line[q_swap] in [2022q1 Homework1 (lab0)](https://hackmd.io/@Risheng/linux2022-lab0) 。
1. I don't need to use three `list_head`
2. It will be better declare `second` in while loop.
3. Use `list_del_init`, `list_add(first, second)`.
### [q_reverse] Reverse elements in queue
#### Instructions:
1. Check `head` exist.
2. Delcare `*prev` 、 `*cuur` 、 `*next` .
#### Tips:
If we want to do the code in the function at lease once, we can use pointer to pointer to `NULL`. After doing the code in the function the pointer which pointers to `NULL` will get meaning, we can compare it in the function condition.
:::spoiler Source Code
```c
/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *prev = head->prev, *curr = head, *next = NULL;
while (next != head) {
next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
:::
### [q_reverseK] Reverse the nodes of the list k at a time
Discussing:
1. Why we can't use`list_del_init(curr)` and `list_add(curr,&list)`, but can use `list_move(curr, &list)` ?
2. Why we can't use `list_add_tail(&list,curr)` and `list_move_tail(&list, curr)`, but can use `list_splice_tail(&list, curr)` ?
3. Is `list_move_tail(&list, curr)` better than change pointers' destinations?
:::spoiler Source Code (Version 1)
```c
/* Reverse the nodes of the list k at a time */
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 *curr = head->next, *list = NULL;
while (curr != head) {
struct list_head *next = NULL;
for (int i = 0; i < k; i++){
next = curr->next;
if (next == head){
list_add(list,curr);
return;
}
list_del_init(curr);
list_add_tail(curr,list);
curr = next;
}
q_reverse(list);
list_add(list,curr);
free(list);
}
}
```
:::
:::spoiler Source Code (Version 2)
```c
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (!head || list_empty(head))
return;
struct list_head *curr = head->next;
while (curr != head){
struct list_head list;
INIT_LIST_HEAD(&list);
for (int i = 0; i < k; i++){
struct list_head *next = curr->next;
if (next == head){
//list_add(&list,curr);
q_reverse(&list);
list_splice_tail(&list, curr);
return;
}
// list_del_init(curr);
// list_add(curr,&list);
list_move(curr, &list);
curr = next;
}
//q_reverse(&list);
// list_add_tail(&list,curr);
// list_move_tail(&list, curr);
list_splice_tail(&list, curr);
//free(&list);
}
}
```
:::
### [q_sort] Sort elements of queue in ascending order
#### Instructions:
==`q_sort` has a same concept as **Merge Two Sorted Lists**.==
Reference Source code [quick-sort.c](https://github.com/sysprog21/linux-list/blob/master/examples/quick-sort.c) in [sysprog21/linux-list](https://github.com/sysprog21/linux-list) programs 。
1. Check linked list in `head` has more than two entry and not empty. If not return it.
2. Use `INIT_LIST_HEAD` to initialize two list structure we made.
3. Use `list_first_entry` to get first entry to set it as pivot.
4. Delete the pivot from linked list (use `list_del`)
5. Compare through all list (`list_for_each_entry_safe`). Use `strncmp` to compare `item->value` to `pivot->value`, and seperate them to each `list_less` and `list_greater`.
6. Call `q_sort` to regress `list_less` & `list_greater`.
7. Add pivot to list
8. Splice `list_less` before pivot in list.
9. Splice `list_greater` after pivot in list.
#### Debug
`cmprint()` error: implicit declaration of function ‘cmpint’
Sol: use `strcmp()` to replace `cmprint()`
```c
list_for_each_entry_safe(item, is, head, list) {
if (cmpint(&item->value, &pivot->value) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
```
or declarate function `cmprint()`
```c
static inline int cmpint(const void *p1, const void *p2)
{
const uint16_t *i1 = (const uint16_t *) p1;
const uint16_t *i2 = (const uint16_t *) p2;
return *i1 - *i2;
}
```
:::spoiler Source Code
```c
/* Sort elements of queue in ascending order */
void q_sort(struct list_head *head)
{
struct list_head list_less, list_greater;
element_t *pivot;
element_t *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, element_t, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (strcmp(item->value, pivot->value) < 0)
list_move_tail(&item->list, &list_less);
else
list_move_tail(&item->list, &list_greater);
}
q_sort(&list_less);
q_sort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
:::
### [q_descend] Remove every node which has a node with a strictly greater value anywhere to the right side of it
:::spoiler Source Code
```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/
return 0;
}
```
:::
### [q_merge] Merge all the queues into one sorted queue, which is in ascending order
**Merge k Sorted Lists** is developed by **Merge Two Sorted Lists**. There is a concept that I don't really understand.
`q_sort` has a same concept as **Merge Two Sorted Lists**.
```graphviz
digraph G {
result[label="1|2|3|4|5|6|7|8", shape=record, height=.1]
node31[label="2|5", shape=record, height=.1]
node32[label="4|6|8", shape=record, height=.1]
node33[label="1|7", shape=record, height=.1]
node34[label="3", shape=record, height=.1,width=.4]
node41[label="2|4|5|6|8", shape=record, height=.1]
node42[label="1|3|7", shape=record, height=.1]
subgraph cluster_3 {
style=filled;
color="#a6cee3";
label="sorted lists";
node32;
node34;
node33;
node31;
}
node31 -> node41
node32 -> node41
node33 -> node42
node34 -> node42
subgraph cluster_2 {
style=filled;
color="#b2df8a";
label="merge";
node41
node41
node42
node42
node41->result
node42->result
}
}
```
#### Instructions:
1. Check `head` is exist and not empty.
2. `list_for_each_entry` is a function which iterates over list entries. In `queue_contex_t` struct, it like a 2D list. `list_head *q` is a one component list, and `list_head chain` is a group list made by many component lists.
3. ==Cut the circular linked list== to doubly linked list.
4. Use function `mergeTwoLists` to merge two lists.
5. `list_entry` is a function which gets the entry for the node.
6. Restructure doubly linked list to circular linked list.
7. Return `q_size` of `(group_list->q)`.
#### Hint:
* include `<stdint.h>` ,when we use `uintptr_t`.
* Function features
* `mergeTwoLists` : Put two lists together, and sequence them.
* `mergesort_list` : Seperate lists.
* Adjust function [`mergeTwoLists()`](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) below.
```c=
struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
c *head = NULL, **ptr = &head, **node;
for (node = NULL; L1 && L2; *node = (*node)->next) {
node = (L1->val < L2->val) ? &L1: &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
In line 4, `*node = (*node)->next` has different data types. `*node` is `struct ListNode*` , and `(*node)->next` is `struct linked_head*`. Change `struct ListNode*` to `struct linked_head*`, and use `list_entry()`to assigment `element_t *L1_entry`.
* Compare `node = (L1_entry->value < L2_entry->value) ? &L1 : &L2` & `node = strcmp(L1_entry->value, L2_entry->value) < 0 ? &L1 : &L2`. Why `strcmp()` doesn't cause "ERROR: Not sorted in ascending order (It might because of unsorted queues are merged or there're some flaws in 'q_merge')" or "ERROR: Removed value c != expected value r"?
:::spoiler Source Code
* Function `mergeTwoLists()`
```c
/* Merge the two lists in a one sorted list. */
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_entry = list_entry(L1, element_t, list);
element_t *L2_entry = list_entry(L2, element_t, list);
node = (L1_entry->value < L2_entry->value) ? &L1 : &L2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
* Function `q_merge()`
```c
/* Merge all the queues into one sorted queue, which is in ascending order */
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
queue_contex_t *entry = list_entry(head, queue_contex_t, chain);
queue_contex_t *c_next = entry->chain.next;
struct list_head *q_head = c_next->q;
while (c_next != head)
{
// struct list_head *q_curr = q_head->next;
// while (q_curr->next != q_head)
// {
// struct list_head *q_next = q_curr->next;
// list_move_tail(q_curr,entry->q);
// q_curr = q_next;
// }
list_splice_tail(q_head,entry->q);
c_next = c_next->chain.next;
}
q_sort(q_head);
int size = q_size(q_head);
return size;
return 0;
}
```
:::
#### Q & A
:::success
Experiment:
```c
#include <stdio.h>
int main(int argc, const char * argv[]) {
int n = 5;
for (int i = 0; i <= n; i++) {
printf("%d\n", i);
}
return 0;
}
```
Output:
```
0
1
2
3
4
5
```
That means `i++` is be done after once cycle of `for` function done.
:::
:::info
In [案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/YA7RMqd6RE2UL8OmmjU9PQ?view#案例探討-LeetCode-21-Merge-Two-Sorted-Lists) case, why we use `struct` in Line 1 ? It should be a function.
```c
struct ListNode *mergeTwoLists(struct ListNode *L1,
struct ListNode *L2) {
struct ListNode *head;
struct ListNode **ptr = &head;
for (; L1 && L2; ptr = &(*ptr)->next) {
if (L1->val < L2->val) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
}
*ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
return head;
}
```
:::
:::info
在[非遞迴的實作](https://hackmd.io/@sysprog/c-linked-list#非遞迴的實作)中，原始的迭代版 merge sort 如下：
```c=
void mergesort_iter(node_t **list) {
node_t *head = *list;
if (!head || !head->next)
return;
node_t *result = NULL;
node_t *stack[1000];
int top = 0;
stack[top] = head;
while (top >= 0) {
node_t *left = stack[top--];
if (left) {
node_t *slow = left;
node_t *fast;
for (fast = left->next; fast && fast->next; fast = fast->next->next)
slow = slow->next;
node_t *right = slow->next;
slow->next = NULL;
stack[++top] = left;
stack[++top] = right;
} else
result = mergeTwoLists(result, stack[top--]);
}
*list = result;
}
```
第12行程式碼意義為何？
:::
Sign in with Wallet
Connect another wallet