---
tags: linux kernel
---
# 2022q1 Homework1 (lab0)
contributed by <[jimmy-liu1021](https://github.com/jimmy-liu1021)>
### Reviewed by `kevinshieh0225`
- 使用 `&node->list` 來取得 dereference list of address. 因為在運算次序中 `derefence ->` 高於 `＆`。這樣不必使用 `// cppcheck-suppress memleak`
- 請善用 linux kernel api `list_for_each`, `list_for_each_entry`, `list_for_each_safe`, `list_for_each_entry_safe`
- `q_remove_head` 重複做了 `list_del(head->next);` 可再簡化。
## 實驗環境
```bash
$ gcc -v
gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
$ 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: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4770K CPU @ 3.50GHz
Stepping: 3
CPU MHz: 800.000
CPU max MHz: 3900.0000
CPU min MHz: 800.0000
BogoMIPS: 6999.56
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 8 MiB
NUMA node0 CPU(s): 0-7
```
## 開發紀錄
:::success
[作業要求](https://hackmd.io/@sysprog/linux2022-lab0) (詳閱連結內容)
- [x] q_new: 建立新的「空」佇列
- [x] q_free: 釋放佇列所佔用的記憶體
- [x] q_insert_head: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)
- [x] q_insert_tail: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)
- [x] q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的節點
- [x] q_release_element: 釋放特定節點的記憶體空間
- [x] q_size: 計算目前佇列的節點總量
- [x] q_delete_mid: 移走佇列中間的節點
- [x] q_delete_dup: 在已經排序的狀況，移走佇列中具備重複內容的節點
- [x] q_swap: 交換佇列中鄰近的節點
- [x] q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點
- [x] q_sort: 以遞增順序來排序鏈結串列的節點
:::
---
### q_new
Create a empty queue.
Return NULL if could not allocate space.
- 流程
1.使用 `malloc()` 分配記憶體位置，並由 `new` 指標指向。如果空間分配失敗，則 `malloc` 會回傳 `NULL`，此時函式回傳`NULL`
2.使用 `list.h` 中的 `INIT_LIST_HEAD` 初始化
:::info
`INIT_LIST_HEAD` 的功能為將 linked list 的 `next` 及 `prev`指向本身
:::
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
:::spoiler q_new 實際程式碼
```c
struct list_head *q_new()
{
element_t *new = malloc(sizeof(element_t));
if (!new)
return NULL;
INIT_LIST_HEAD(&(new->list));
// cppcheck-suppress memleak
return &(new->list);
}
```
:::
---
### q_free
Free all storage used by queue
- 流程
1.先檢查 `head` 是否為空，若為空則直接`return` 結束函式
2.使用 `container_of` 取出節點的記憶體位置，並逐一釋放空間。
3.釋放 `head` 的記憶體空間
:::info
參考 [Linux 核心原始程式碼巨集: container_of](/odsx15lMRDiqsuQDL8LE8g)，得知 `container_of` 可以用來得到包含 `ptr` 之 `object` 的起始記憶體位址
:::
:::spoiler q_free 實際程式碼
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *ptr = l->next;
while (ptr != l) {
element_t *node = container_of(ptr, element_t, list);
ptr = ptr->next;
q_release_element(node);
}
element_t *node = container_of(ptr, element_t, list);
free(node);
}
```
:::
---
### q_insert_head
Attempt to insert element at head of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
- 流程
1.如果 `head` 為 `NULL` 則 `return false`
2.使用 `malloc()` 分配 `emelent_t` 大小的記憶體空間，若失敗則 `return false`
3.使用 `strlen()` 取得字串長度，並分配複製字串所需的空間
:::info
分配時要多一個位元組存放 NULL pointer
:::
4.使用 `list.h` 中的函式 `list_add()` 將節點加在 `head`之後
:::info
`list_add()` 的功能為，將 `node` 接在 `head` 之後，並把 link 接好
:::
```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;
}
```
:::spoiler q_insert_head 實際程式碼
```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 s_size = strlen(s);
char *s_copy = malloc(s_size + 1);
if (!s_copy) {
free(node);
return false;
}
memcpy(s_copy, s, s_size);
s_copy[s_size] = 0;
node->value = s_copy;
list_add(&node->list, head);
return true;
}
```
:::
---
### q_insert_tail
Attempt to insert element at tail of queue.
Return true if successful.
Return false if q is NULL or could not allocate space.
Argument s points to the string to be stored.
The function must explicitly allocate space and copy the string into it.
- 流程
`q_insert_tail()` 與 `q_insert_head()` 幾乎相同，區別只有加入節點時使用的是 `list_add_tail()`
:::spoiler q_insert_tail 實際程式碼
```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 s_size = strlen(s);
char *s_copy = malloc(s_size + 1);
if (!s_copy) {
free(node);
return false;
}
memcpy(s_copy, s, s_size);
s_copy[s_size] = 0;
node->value = s_copy;
list_add_tail(&node->list, head);
return true;
}
```
:::
---
### q_remove_head
Attempt to remove element from head of queue.
Return target element.
Return NULL if queue is NULL or empty.
If sp is non-NULL and an element is removed, copy the removed string to *sp
(up to a maximum of bufsize-1 characters, plus a null terminator.)
NOTE: "remove" is different from "delete"
The space used by the list element and the string should not be freed.
The only thing "remove" need to do is unlink it.
REF: https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove
- 流程
1.檢查 `head` 是否為 `NULL` 及 queue 是否為空，若成立則回傳 `NULL`
2.因為要用到第一個節點的 `value` ，所以用 `container_of` 取出第一個節點的位址，並使用 `memcpy` 將其所存的字串複製下來，複製的大小根據 `bufsize`
:::spoiler q_remove_head 實際程式碼
```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 = container_of(head->next, element_t, list);
if (!sp) {
list_del(head->next);
return node;
}
memcpy(sp, node->value, bufsize - 1);
list_del(head->next);
sp[bufsize - 1] = 0;
return node;
}
```
:::
---
### q_remove_tail
Attempt to remove element from tail of queue.
Other attribute is as same as q_remove_head.
- 流程
與 `q_remove_head` 相似，不同處為取出的點為 `head->prev` 即最後一個節點
:::spoiler q_remove_tail 實際程式碼
```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 = container_of(head->prev, element_t, list);
if (!sp) {
list_del(head->prev);
return node;
}
memcpy(sp, node->value, bufsize - 1);
list_del(head->prev);
sp[bufsize - 1] = 0;
return node;
}
```
:::
---
### q_size
Return number of elements in queue.
Return 0 if q is NULL or empty
- 流程
使用 `list.h` 中的巨集函式 `list_for_each()` 走訪每個節點，以計算linked list的長度
:::spoiler q_size 實際程式碼
```c
int q_size(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *li;
list_for_each (li, head)
len++;
return len;
}
```
:::
---
### q_delete_mid
Delete the middle node in list.
The middle node of a linked list of size n is the
⌊n / 2⌋th node from the start using 0-based indexing.
If there're six element, the third member should be return.
Return true if successful.
Return false if list is NULL or empty.
- 流程
1.參考 [你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ)，案例探討： Leetcode 2095. Delete the Middle Node of a Linked List，使用快慢指標的技巧
:::info
此案例中，快指標每一次往前進兩個節點，而慢指標每一次往前進一個節點。如此一來，當快指標指向最後一個節點時，慢指標恰好指向中間的節點
:::
2.並且搭配 indirect pointer 的技巧，省去配置暫時節點的空間
:::spoiler q_delete_mid 實際程式碼
```c
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
if (!head)
return false;
if (list_empty(head))
return false;
struct list_head **indir_slow = &head->next;
for (struct list_head *fast = head->next;
head != fast && head != fast->next; fast = fast->next->next) {
indir_slow = &(*indir_slow)->next;
}
element_t *remove_point = container_of(*indir_slow, element_t, list);
list_del(*indir_slow);
q_release_element(remove_point);
return true;
}
```
:::
---
### q_delete_dup
Delete all nodes that have duplicate string,
leaving only distinct strings from the original list.
Return true if successful.
Return false if list is NULL.
Note: this function always be called after sorting, in other words,
list is guaranteed to be sorted in ascending order.
- 流程
1.取出首個節點的字串，接著將字串跟後續節點的字串依序比較是否相同，若相同則刪去
2.並以 `dup_flag` 去記錄刪去這個行為是否有被執行，若有 (表示有與首個節點重複的點) 則將首個節點也刪去
:::info
實作時原本以為只需要刪去重複的多餘字串 (留下1個，e.g. 112233 留下123) 即可，但在 `make test` 時失敗，才發現要刪去所有重複的(e.g. 11223345 只留下 45)，使用了`flag` 的方式去紀錄，但是造成程式碼大量重複
:::
:::spoiler q_delete_dup 實際程式碼
```c
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
struct list_head *ptr1 = head->next, *ptr2 = ptr1->next;
element_t *node1 = container_of(ptr1, element_t, list);
bool dup_flag = false;
for (; ptr2 != head; ptr2 = ptr1->next) {
element_t *node2 = container_of(ptr2, element_t, list);
if (strcmp(node1->value, node2->value) == 0) {
list_del(ptr2);
q_release_element(node2);
dup_flag = true;
} else {
if (dup_flag) {
list_del(ptr1);
q_release_element(node1);
dup_flag = false;
}
ptr1 = ptr2;
node1 = container_of(ptr1, element_t, list);
}
}
if (dup_flag) {
list_del(ptr1);
q_release_element(node1);
}
return true;
}
```
:::
---
### q_swap
Attempt to swap every two adjacent nodes.
- 流程
Step1. 將 `ptr` 指標指向`head` ，將 `tmp` 指標指向`third`
```graphviz
digraph {
rankdir=LR
ptr[shape=plaintext]
ptr->head[color=red]
head->first->second->third
third->second->first->head[color=blue]
tmp[shape=plaintext]
tmp->third[color=red]
}
```
Step2. `second` 的 `next` 指向 `first`
```graphviz
digraph {
rankdir=LR
ptr[shape=plaintext]
ptr->head
head
first
second
third
head->first->second
third->second->first->head[color=blue]
second->first[color=red,label=next]
tmp[shape=plaintext]
tmp->third
}
```
Step3. `head` 的 `next` 指向 `second`
```graphviz
digraph {
rankdir=LR;
ptr[shape=plaintext]
ptr->head
head
first->second
third->second->first->head[color=blue]
second->first
tmp[shape=plaintext]
tmp->third
head->second[color=red,label=next]
}
```
Step4. `first` 的 `next` 指向 `third`，以上步驟將 `next` 皆布置完畢
```graphviz
digraph {
rankdir=LR;
ptr[shape=plaintext]
ptr->head
head
third->second->first->head[color=blue]
second->first
tmp[shape=plaintext]
tmp->third
head->second
first->third[color=red,label=next]
}
```
Step5. 將各個節點的 `prev` 接好，並將 `ptr` 指向 `third` 準備進行下一個循環
```graphviz
digraph {
rankdir=LR;
head
third->first->second->head[color=red]
second->first
ptr[shape=plaintext]
ptr->third[color=red]
head->second
first->third
}
```
:::spoiler q_swap 實際程式碼
```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 *ptr = head;
while (ptr->next != head && ptr->next->next != head) {
struct list_head *tmp = ptr->next->next->next;
ptr->next->next->next = ptr->next;
ptr->next = ptr->next->next;
ptr->next->next->next = tmp;
ptr->next->next->next->prev = ptr->next->next;
ptr->next->next->prev = ptr->next;
ptr->next->prev = ptr;
ptr = ptr->next->next;
}
}
```
:::
---
### q_reverse
Reverse elements in queue
No effect if q is NULL or empty
This function should not allocate or free any list elements
(e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
It should rearrange the existing ones.
- 流程
將每個節點與其下一個節點做 swap 即可達成整個 queue reverse
:::spoiler q_reverse 實際程式碼
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *tmp = NULL, *ptr = NULL;
for (ptr = head->next; ptr != head; ptr = ptr->prev) {
tmp = ptr->next;
ptr->next = ptr->prev;
ptr->prev = tmp;
}
tmp = ptr->next;
ptr->next = ptr->prev;
ptr->prev = tmp;
}
```
:::
---
### q_sort
Sort elements of queue in ascending order
No effect if q is NULL or empty. In addition, if q has only one element, do nothing.
- 流程
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](/YA7RMqd6RE2UL8OmmjU9PQ) 案例探討: LeetCode 21.Merge Two Sorted Lists
:::spoiler q_sort 實際程式碼
```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;
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;
struct list_head *left = mergesort_list(head), *right = mergesort_list(mid);
return mergeTwoLists(left, right);
}
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = mergesort_list(head->next);
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
```
:::
Sign in with Wallet
Connect another wallet