---
tags: linux 2023
---
# 2023q1 Homework1 (lab0)
contributed by < `randyuncle` >
:::danger
變更登記於 https://hackmd.io/@sysprog/linux2023-homework1 的超連結，要用「固定網址」(參見 用固定網址發布筆記)，也就是如 https://hackmd.io/@itsme/XXXX 的形式，設定公開發表。
:notes: jserv
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
CPU family: 6
Model: 158
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 10
CPU max MHz: 4100.0000
CPU min MHz: 800.0000
BogoMIPS: 4399.99
```
## `queue.c` 開發過程
:::info
目前 make test 分數：95/100
:::
### `q_new`
首先以 `malloc` 來配置 `struct list_head` 大小的記憶體空間給最初的節點，之後再將其以 `list.h` 的內部 function `INIT_LIST_HEAD` 把該節點的內容初始化。
:::warning
改進漢語描述。
:notes: jserv
:::
除此之外，為了防止 `malloc` 無法配置記憶體空間的問題，所以加了一個 if-statement 判斷此節點是否為 NULL，以防在做 `INIT_LIST_HEAD` 的初始化時出錯。
```c
struct list_head *q_new()
{
struct list_head *head =
(struct list_head *) malloc(sizeof(struct list_head));
if (head)
INIT_LIST_HEAD(head);
return head;
}
```
### `q_free`
以 `list.h` 中的 macro `list_for_each_entry_safe` 對輸入進來的 `struct list_head *head` 做迭代。
其中，將所有經過的節點的 :
* `struct list_head list` : 以 `list.h` 的 function `list_del` 刪掉。
* `char *value` : 以 `queue.h` 的 function `q_release_element` 釋放掉。
除此之外，為了防止輸入進來的 `struct list_head *head` 是 NULL，所以多加了一個 if-statement 判斷其是否為 NULL。
```c
void q_free(struct list_head *l)
{
if (l) {
// if head exists, clean the queue.
element_t *iterator, *next;
list_for_each_entry_safe (iterator, next, l, list) {
list_del(&iterator->list);
q_release_element(iterator);
}
free(l);
}
}
```
### `q_insert_head` / `q_insert_tail`
這兩個 function 的<s>實做</s> 實作是大同小異的，都是先新增一個 `element_t` 型態的 node 將輸入進 function 的` struct list_head *head`、`char *s` 儲存。
:::warning
注意 [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::
之後，再使用 `list.h` 的 function 將 `element_t` 內的 list 加入到 queue 之中。其中，`q_insert_head` 用的是 `list_add` ; `q_insert_tail` 使用 `list_add_tail`。
```c
bool q_insert(struct list_head *head, char *s){
if (!head || !s)
return false;
element_t *new = (element_t *) malloc(sizeof(element_t));
if (!new)
return false; // no memory space for `new`
int s_len = strlen(s) + 1;
new->value = (char *) malloc(s_len * sizeof(char));
if (!new->value) {
free(new);
return false; // no memory space for `new->value`
}
memcpy(new->value, s, s_len); // insert value
/**
* depends on `element_t *new` inserts at head or tail of queue
list_add(&new->list, head); // insert at head of queue
list_add_tail(&new->list, head); // insert at tail of queue
*/
return true;
}
```
### `q_size`
採用 list.h 的 function `list_for_each` 做 linked-list 的 traverse，達成 queue 長度的計算。
```c
int q_size(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
int size = 0;
struct list_head *p;
list_for_each (p, head)
size++;
return size;
}
```
### `q_remove_head` / `q_remove_tail`
這兩個 function 的實作是大同小異的。差別在於 `q_remove_head` 是用 list.h 中的 `list_first_entry` 去找到要被 移走的頭部節點 ; `q_remove_tail` 是用 list.h 中的 `list_last_entry` 去找到要被移走的尾部節點。
```c
element_t *q_remove(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL; // `head` is NULL, or there's no list in `head`
/**
* depends on remove head or tail node
element_t *remove = list_first_entry(head, element_t, list);
element_t *remove = list_last_entry(head, element_t, list);
*/
list_del(&remove->list);
if (sp) {
memcpy(sp, remove->value, bufsize);
sp[bufsize - 1] = '\0';
}
return remove;
}
```
### `q_delete_mid`
在尋找中間節點的實作當中，一開始是參考了 [Floyd’s Cycle detection](https://en.wikipedia.org/wiki/Cycle_detection) 的理論，運用快慢指標的方式找到中間節點。
但是，由於此程式的 queue 是用 circular double linked-list 的形式所構成，所以就稍微改變了一下實作的方式成以下：
1. 令兩個 `struct list_head` 的指標 `foreward` 和 `backward` 。前者的作用是從 queue 的 head 往後跑一個節點 ; 後者的作用是從 queue 的 tail 往前跑一個節點。
2. 當兩個指標指到同一個節點時，或者是 `foreward` 指標的下一個節點是 `backward` 時，則 `foreward` 指標指到的節點為該 queue 的中間節點。
```c
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false; // `head` is NULL, or there's no list in `head`
/*if the foreward pointer hits the backward pointer, then they're in the
* middle of the list*/
struct list_head *foreward = head->next, *backward = head->prev;
for (; foreward != backward && foreward->next != backward;
foreward = foreward->next, backward = backward->prev)
;
list_del(foreward);
q_release_element(container_of(foreward, element_t, list));
return true;
}
```
### `q_delete_dup`
運用到了 list.h 中的 macro `list_for_each_entry_safe` 來對 `element_t` structure 的 linked-list `list` 做 traverse 。其中，以 `element_t *iterator` 當作該 macro 中的 entry ，`element_t *next` 當作該 macro 中的 safe 。並且，根據每次的迭代，會有以下判斷的方式判斷是否有重複的字串：
* 當 `next != head` 且 `next->value` == `iteration->value` 時：
* 進入 do-while 迴圈中，把 `next` 指標指到的節點刪除，並將 `next` 指標移到他的下一個節點上，以相通得判斷式判斷該節點的 `value` 是否也為該重複的字串。
* 迴圈結束後，把目前 iterator 指到的節點刪除，回去 `list_for_each_entry_safe` macro 做迭代。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false; // `head` is NULL, or there's no list in `head`
element_t *iterator, *next;
/*note that the list is sorted*/
list_for_each_entry_safe (iterator, next, head, list) {
if (&next->list != head && !strcmp(iterator->value, next->value)) {
do {
element_t *next_to_safe =
list_entry(next->list.next, element_t, list);
list_del(&next->list);
q_release_element(next);
next = next_to_safe;
} while (&next->list != head &&
!strcmp(iterator->value, next->value));
list_del(&iterator->list);
q_release_element(iterator);
}
}
return true;
}
```
### `q_swap`
使用兩個指標 `struct list_head *curr` 和 `struct list_head *next` ，分別代表兩個要被互相交換的節點，以及一個 for 迴圈做 `struct list_head` structure 的 linked-list traverse
其中，`curr` 和 `next` 任兩個指標在未到達 `struct list_head *head` 的情況下，會先以 list.h 中的 function `list_move` 將 `curr` 和 `next` 指向的節點做交換。之後，再將 `curr` 指向自己的下一個指標 ; `next` 指向 `curr` 的下一個指標，避免有交換到已經做過交換的節點。
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return; // `head` is NULL, or there's no list in `head`
struct list_head *curr = head->next, *next = curr->next;
for (; curr != head && next != head; curr = curr->next, next = curr->next)
list_move(curr, next);
}
```
### `q_reverse`
使用 list.h 的 macro `list_for_each_safe` 去 traverse 所有的 `struct list_head` structure 的 linked-list，並將每一個 traverse 到的節點都使用 list.h 的 function `list_move` 搬到整個 queue 的源頭，也就是成為 `struct list_head *head` 後一個節點。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return; // `head` is NULL, or there's no list in `head`
struct list_head *iterator, *next;
/*move each item the iterator points to to the head*/
list_for_each_safe (iterator, next, head)
list_move(iterator, head);
}
```
### `q_reverse_k`
目前使用的方法是用 list.h 的 macro `list_for_each_safe` 去 traverse 所有的 `struct list_head` structure 的 linked-list，並在其中加入一個計數器來計是否已經經過 k 個節點。如果已經經過 k 個節點，則會用前一個 function `q_reverse` 去把該 k 個節點反轉。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return; // `head` is NULL, or there's no list in `head`
struct list_head *iterator, *next, *start = head, dummy;
INIT_LIST_HEAD(
&dummy); // pointer dummy serves as same as pointer head does
int i = 0;
list_for_each_safe (iterator, next, head) {
i++;
if (i < k)
continue;
list_cut_position(&dummy, start,
iterator); // cut k node of the list out as an
// independent list to be reverse
q_reverse(&dummy);
list_splice_init(&dummy,
start); // take dummy back to the original list
start = next->prev;
i = 0;
}
}
```
### `q_sort`
在本程式中的 `q_sort` 我採用的是 merge sort 。其中，製作 merge sort 的方式主要是參考了[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C) 中的 Merge Sort 的實作。也因此，我把 `q_sort` 拆成了三個 function -- `q_sort` 、`divide`、`merge_two_list` 。
為了能夠不讓指標會因為 circular linked-list 的特性跑到 `struct list_head *head` 的關係，在 function `q_sort` 中就會先將 queue 的尾端節點和 `struct list_head *head` 的連結斷掉，使其失去 circular 的特性，方便進行 linked-list 的 divide。最後，在 queue 已經 sort 完後，再重新把 queue 變成 circular linked-list。
```c
void q_sort(struct list_head *head)
{
// merge sort machemic
if (!head || list_empty(head) || list_is_singular(head))
return; // `head` is NULL, no list in `head`, or one element
struct list_head *end = head->prev;
// make the list no longer be circular
end->next = NULL;
head->next->prev = NULL;
// start to sort
head->next = divide(head->next, end);
// make the list to be circular again (move the head back)
struct list_head *curr;
for (curr = head; curr->next; curr = curr->next)
curr->next->prev = curr;
curr->next = head;
curr->next->prev = curr;
}
```
#### `divide`
在 `q_sort` 使 queue 失去 circular linked-list 的特性後，會先進入 `divide` function 。
divide function 主要的目的是用來找一個 linked-list 的中間節點，從而將其拆成兩個 linked-list ，再分別代入 `divide` 做遞迴。等到 linked-list 被拆成只有一個節點的時候，就會將兩個相鄰的 linked-list 以 `merge_two_list` function 統合成排序好的 linked-list。
```c
struct list_head *divide(struct list_head *head, struct list_head *end)
{
if (head == end)
return head;
// find middle point
struct list_head *foreward = head, *backward = end;
for (; foreward != backward && foreward->next != backward;
foreward = foreward->next, backward = backward->prev)
;
if (foreward == backward) // the list has odd nodes
backward = backward->next;
// make the list no longer be circular
foreward->next = NULL;
backward->prev = NULL;
// keep divide until hit the break point
struct list_head *left = divide(head, foreward);
struct list_head *right = divide(backward, end);
// conquer the partitions
return merge_two_list(left, right);
}
```
#### `merge_two_list`
作法源自於[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)的一個片段 -- `從 Linux 核心的藝術談起 -- 案例探討: LeetCode 21. Merge Two Sorted Lists` ，也就是利用間接指標的概念將要 merge 的節點一個一個串起來。
```c
struct list_head *merge_two_list(struct list_head *left,
struct list_head *right)
{
// reference: 你所不知道的 C 語言: linked list 和非連續記憶體
struct list_head *head = NULL;
struct list_head **p = &head;
for (; left && right; p = &((*p)->next)) {
element_t *l = list_entry(left, element_t, list);
element_t *r = list_entry(right, element_t, list);
if (strcmp(l->value, r->value) < 0) {
*p = left;
left = left->next;
} else {
*p = right;
right = right->next;
}
}
*p = (struct list_head *) ((uintptr_t) left |
(uintptr_t) right); // <stdint.h>
return head;
}
```
### `q_descend`
根據 [Leetcode 2487. Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/) 的例子可以看出，`q_descend` 運行完以後的 sorted linked-list 會呈嚴格降冪排列。
因此，此塊的實作就以兩個 `element_t` 型態的指標：`*p`, `*c_max` 配合一個 for 迴圈對 queue 做逆向 traverse 。其中，當指標 `*p` 指向的節點的 `value` 比起 `*c_max` 指到的來得小或者是一樣的話，就會將其抹除 ; 反之，則將 `*c_max`
更新為 `*p` 指到的節點。
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0; // `head` is NULL, or there's no list in `head`
// this section cares about value in 'element_t' structure
struct list_head *curr = head->prev;
element_t *p, *c_max = list_entry(curr, element_t, list);
for (; c_max->list.prev != head;) {
p = list_entry(c_max->list.prev, element_t, list);
if (strcmp(p->value, c_max->value) <= 0) {
list_del(&p->list);
q_release_element(p);
} else
c_max = p;
}
return q_size(head);
}
```
### `q_merge`
將 `queue_contex_t` structure 各個分段的 queue 以 list.h 的 function `list_splice_init` 接在以 `queue_contex_t *main_q` 的 queue 之中。
之後，再使用前面寫的 `q_sort` function 將 `queue_contex_t *main_q` 的 queue 做重新排列。
```c
int q_merge(struct list_head *head)
{
if (!head || list_empty(head))
return 0; // `head` is NULL, or there's no list in `head`
if (list_is_singular(head))
return list_entry(head->next, queue_contex_t, chain)->size;
// merging by 'q_context_t' structure
queue_contex_t *main_q = list_entry(head->next, queue_contex_t, chain);
// 分段合併
for (struct list_head *curr = head->next->next; curr != head;
curr = curr->next) {
queue_contex_t *c = list_entry(curr, queue_contex_t, chain);
list_splice_init(c->q, main_q->q);
main_q->size += c->size;
c->size = 0;
}
// sorting
q_sort(main_q->q);
return main_q->size;
}
```
Sign in with Wallet
Connect another wallet