---
tags: linux2022, linux
---
# 2022q1 Homework1 (lab0)
contributed by < `Andy240881` >
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0)
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 6.5.0-2ubuntu1~18.04) 6.5.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz
Stepping: 10
CPU MHz： 2267.463
CPU max MHz: 3201.0000
CPU min MHz: 800.0000
BogoMIPS: 6399.96
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 12288K
NUMA node0 CPU(s): 0-11
```
## 開發過程
### q_new
* 檢查 malloc 是否成功。
* 觀摩同學 [laneser](https://hackmd.io/@laneser/linux2022_lab0) 的開發紀錄後發現可以使用 `INIT_LIST_HEAD()` 使得程式碼更加簡潔。
```c
struct list_head *q_new()
{
struct list_head *head = malloc(sizeof(struct list_head));
if (!head) {
return NULL;
}
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
* 檢查 l 是否為空。
* 利用 list.h 中的 `list_for_each_entry_safe()` 迭代刪除目標，並使用 queue.c 中既有的 `q_release_element` 釋放 queue 中的每個 node。
* queue 的 head 也要記得釋放空間。
```c
void q_free(struct list_head *l)
{
if (l == NULL) {
return;
}
element_t *iter, *tmp;
list_for_each_entry_safe (iter, tmp, l, list)
q_release_element(iter);
free(l);
}
```
### q_insert_head
* 檢查 head 是否為空。
* 建立要插入的 node，並將 s 複製到對應欄位。
* 使用 `list_add` 將新的節點連結至 queue 的開頭。
```cpp
bool q_insert_head(struct list_head *head, char *s)
{
if (head == NULL) {
return false;
}
element_t *item = malloc(sizeof(element_t));
if (item == NULL) {
return false;
}
item->value = strdup(s);
if (item->value == NULL) {
q_release_element(item);
return false;
}
list_add(&item->list, head);
return true;
}
```
### q_insert_tail
* 將 q_insert_head 中的 `list_add` 抽換成`list_add_tail`。
```cpp
bool q_insert_tail(struct list_head *head, char *s)
{
if (head == NULL) {
return false;
}
element_t *item = malloc(sizeof(element_t));
if (item == NULL) {
return false;
}
item->value = strdup(s);
if (item->value == NULL) {
q_release_element(item);
return false;
}
list_add_tail(&item->list, head);
return true;
}
```
### q_remove_head
* 需要加上 `cppcheck-suppress nullPointer` 的註解來關閉 cppcheck 的 null pointer 錯誤。
* 一開始誤以為 queue 的每個節點皆是 `element_t` ，但事實上 head 是不含 value 欄位的 `list_head`，因此在使用 `container_of()` 時第一個參數要填 `head->next` 才會得到正確的節點位址。
* 使用 `list_del_init` 移除queue的第一個節點，並讓該節點的 prev 與 next 指向自己。
```cpp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
// cppcheck-suppress nullPointer
element_t *q = container_of(head->next, element_t, list);
if (!q) {
return NULL;
}
list_del_init(head->next);
if (sp != NULL) {
strncpy(sp, q->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return q;
}
```
### q_remove_tail
* 將 `q_remove_head` 中的操作對象 head->next (第一個節點) 換成 head->prev (最後一個節點) 即可。
```cpp
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
// cppcheck-suppress nullPointer
element_t *q = container_of(head->prev, element_t, list);
if (!q) {
return NULL;
}
list_del_init(head->prev);
if (sp != NULL) {
strncpy(sp, q->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return q;
}
```
### q_size
```cpp
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
* 利用 q_size() 取得 queue 的長度。
* 使用 list.h 中的 `list_for_each_entry_safe()` 遍歷 queue 並刪除第 ⌊n / 2⌋ 個節點。
* 先 remove 節點後，再delete。
```cpp
bool q_delete_mid(struct list_head *head)
{
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
int len = q_size(head);
if (len == 0)
return NULL;
int i = 0;
element_t *iter, *tmp;
list_for_each_entry_safe (iter, tmp, head, list)
if (i != len / 2 ) {
i++;
} else {
list_del_init(&iter->list);
q_release_element(iter);
break;
}
return true;
}
```
### q_reverse
```cpp
void q_reverse(struct list_head *head)
{
if (head == NULL)
return;
struct list_head *pre = head->prev;
struct list_head *current = head;
struct list_head *next = NULL;
next = current->next;
current->next = pre;
current->prev = next;
pre = current;
current = next;
while (current != head) {
next = current->next;
current->next = pre;
current->prev = next;
pre = current;
current = next;
}
}
```
:::warning
思考 circular doubly-linked list 的特性，上述程式碼可更精簡，並善用 Linux List APIs
:notes: jserv
:::
* 利用 circular doubly-linked list 可以反向遍歷的特性，從最後一個節點開始，以反向將每個節點用 `list_move_tail` 放到 list 的最後面，達到 reverse 的效果。
```cpp
void q_reverse(struct list_head *head)
{
if (head == NULL)
return;
if (list_empty(head))
return;
struct list_head *current = head->prev;
struct list_head *next = NULL;
next = current->prev;
list_move_tail(current, head);
current = next;
while (current != head) {
next = current->prev;
list_move_tail(current, head);
current = next;
}
}
```
:::warning
上方程式碼尚可更精簡，請繼續改進
:notes: jserv
:::
* 參考同學 [kevinshieh0225](https://hackmd.io/@Masamaloka/2022q1-hw1#q_reverse) 的做法，使用 `do-while` 讓程式碼更加精簡。
* 加入 singular 的判斷，若 list 長度為 1 ，則不用 reverse 。
```cpp
void q_reverse(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return;
struct list_head *current = head->prev;
do{
struct list_head *next = current->prev;
list_move_tail(current, head);
current = next;
}while (current != head);
}
```
### q_swap
* 遍歷 list 的每個節點，且將節點倆倆交換（每個節點僅被交換一次）。
* while 迴圈的終止條件會分別因為list長度為奇數或偶數而有不同的情況。
```cpp
void q_swap(struct list_head *head)
{
// https://leetcode.com/problems/swap-nodes-in-pairs/
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *current = head->next;
struct list_head *next = NULL;
while (current != head && current->next != head) {
next = current->next;
list_move_tail(next, current);
current = current->next;
}
}
```
### q_delete_dup
* 原本沒想清楚，只有單純比較相鄰的兩個節點，若相同則刪除，但沒有考慮到有兩個以上的節點重複的狀況。
* 參考同學 [laneser](https://hackmd.io/@laneser/linux2022_lab0)的做法，用 `flag` 紀錄是否有重複的情形發生。
* 遍歷 list 時，若 flag = 1 （代表自己與上個節點相同）或是與隔壁節點 value 相同，就會刪除目前遍歷到的節點。
```cpp
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;
if (list_is_singular(head))
return true;
element_t *iter, *tmp;
int flag = 0;
list_for_each_entry_safe (iter, tmp, head, list)
if ((iter->list.next != head) &&
!strcmp(iter->value,
// cppcheck-suppress nullPointer
list_entry(iter->list.next, element_t, list)->value)) {
list_del(&iter->list);
q_release_element(iter);
flag = 1;
} else if (flag) {
list_del(&iter->list);
q_release_element(iter);
flag = 0;
}
return true;
}
```
### q_sort
* 利用 linux 現有的 list_sort。
* TODO: 了解 linux 的 list_sort 原理。
```cpp
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
list_sort(NULL, head, sort_comp);
}
```
Sign in with Wallet
Connect another wallet