---
tags: linux2022
---
# 2022q1 Homework1 (lab0)
contributed by < Ahsen-lab >
## 實驗環境
```shell
$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0
Copyright (C) 2019 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
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 165
Model name: Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz
Stepping: 5
CPU MHz: 2904.002
BogoMIPS: 5808.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 48 MiB
NUMA node0 CPU(s): 0-3
```
## 作業要求
> [作業要求](https://hackmd.io/@sysprog/linux2022-lab0#-作業要求)
[queue.c](https://github.com/sysprog21/lab0-c/blob/master/queue.c) 僅提供介面 ([interface](https://en.wikipedia.org/wiki/Interface-based_programming)) 但尚未有完整程式實作，需要由學員補完並逐步精進，包含以下:
* `q_new`: 建立新的「空」佇列。
* `q_free`: 釋放佇列所佔用的記憶體。
* `q_insert_head`: 在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)。
* `q_insert_tail`: 在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)。
* `q_remove_head`: 在佇列開頭 (head) 移去 (remove) 給定的節點。
* `q_remove_tail`: 在佇列尾端 (tail) 移去 (remove) 給定的節點。
* `q_release_element`: 釋放特定節點的記憶體空間。
* `q_size`: 計算目前佇列的節點總量。
* `q_delete_mid`: 移走佇列中間的節點，詳見 [LeetCode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)。
* `q_delete_dup`: 在已經排序的狀況，移走佇列中具備重複內容的節點，詳見 [LeetCode 82. Remove Duplicates from Sorted List II](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/)。
* `q_swap`: 交換佇列中鄰近的節點，詳見 [LeetCode 24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/)。
* `q_reverse`: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點。
* `q_sort`: 以==遞增順序==來排序鏈結串列的節點，可參閱 [Linked List Sort](https://npes87184.github.io/2015-09-12-linkedListSort/) 得知實作手法。
## 開發過程
### q_new
建立新的「空」佇列，使用`malloc`分配記憶體空間給`head`，再用`INIT_LIST_HEAD` function來初始化`head`，需要注意`malloc`有可能會 fail，若分配記憶體空間失敗，則回傳`NULL`。
```c
/*
* Create empty queue.
* Return NULL if could not allocate space.
*/
struct list_head *q_new()
{
struct list_head *head;
head = (struct list_head *) malloc(sizeof(struct list_head));
if (!head)
return NULL;
INIT_LIST_HEAD(head);
return head;
}
```
### q_free
釋放佇列所佔用的記憶體
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *pos, *q;
element_t *curr = NULL;
list_for_each_safe (pos, q, l) {
curr = list_entry(pos, element_t, list);
list_del(pos);
if (curr != NULL) {
free(curr);
}
}
free(q);
}
```
一開始對 Linux List Management API 還不是很熟，所以使用上方這種比較多此一舉的方式來實作，用 `list_for_each_safe` 走訪每個 `node` 並用 `list_entry` 取出對應的 `element`，然後釋放 `element` 所佔的記憶體空間。
後來重新讀了 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 檔裡的 API 說明，以及參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0) 的設計，改為使用 `list_for_each_entry_safe` API 來實作，程式碼如下，變得簡潔許多。
```c
/* Free all storage used by queue */
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *curr, *tmp;
list_for_each_entry_safe (curr, tmp, l, list) {
free(curr->value);
free(curr);
}
free(l);
}
```
### q_insert_head
在佇列開頭 (head) 插入 (insert) 給定的新節點
```c
bool q_insert_head(struct list_head *head, char *s)
{
element_t *newh = (element_t *) malloc(sizeof(element_t));
if (!newh || !head)
return false;
newh->value = (char *) calloc(strlen(s) + 1, sizeof(char));
if (!(newh->value)) {
free(newh->value);
free(newh);
return false;
}
memcpy(newh->value, s, strlen(s));
list_add(&newh->list, head);
return true;
}
```
我的作法是分配一段記憶體空間給一個新的 `element` ，再分配一段空間給 `element` 的成員變數 `char *value` 用來儲存字串，一開始我是使用 `calloc` 來分配空間給字串，原因是 `calloc` 分配的空間是一個 `array` ，而且會自動將 `array` 中的每個 `bits` 都初始化為 `0`，在字元中 `0` 與 `NULL` 相等，只要分配 ==strlen(str) + 1== 長度的 `array`，再將字串複製進去，就不用手動在字串尾端加上 `NULL`。
```c
#include <stdlib.h>
void *calloc(size_t nmemb, size_t size);
```
>* [C99](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) [7.20.3.1] **The calloc function**
> - The calloc function allocates space for an array of **nmemb** objects, each of whose size is **size**. The space is initialized to all bits zero.
但在實作過程中有遇到一個問題，若使用 `calloc` 來分配空間給 `char *value` ，在 `q_free` function 中 free `char *value` 會出現 error :
:::danger
Error: Attempted to free unallocated block
:::
但若是使用 `malloc` 則不會有這個問題，所以後來我改成下方那種寫法。
```c
/*
* 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.
*/
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
int len = strlen(s);
element_t *newh = (element_t *) malloc(sizeof(element_t));
if (!newh)
return false;
newh->value = (char *) malloc(len + 1);
if (!(newh->value)) {
q_release_element(newh);
return false;
}
memcpy(newh->value, s, len);
newh->value[len] = '\0';
list_add(&newh->list, head);
return true;
}
```
:::warning
TODO : 造成 `malloc` 和 `calloc` 會導致不同結果的原因目前還在追蹤中。
:::
### q_insert_tail
在佇列尾端 (tail) 插入 (insert) 給定的新節點
```c
/*
* 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.
*/
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
int len = strlen(s);
element_t *newt = (element_t *) malloc(sizeof(element_t));
if (!newt)
return false;
newt->value = (char *) malloc(len + 1);
if (!(newt->value)) {
q_release_element(newt);
return false;
}
memcpy(newt->value, s, len);
newt->value[len] = '\0';
list_add_tail(&newt->list, head);
return true;
}
```
實作概念與 `q_insert_head` 相同，只是將 `list_add` 換成 `list_add_tail`。
### q_remove_head
在佇列開頭 (head) 移去 (remove) 給定的節點
```c
/*
* 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
*/
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_first_entry(head, element_t, list);
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->next);
return entry;
}
```
### q_remove_tail
在佇列尾端 (tail) 移去 (remove) 給定的節點
```c
/*
* Attempt to remove element from tail of queue.
* Other attribute is as same as q_remove_head.
*/
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *entry = list_last_entry(head, element_t, list);
if (sp) {
strncpy(sp, entry->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(head->prev);
return entry;
}
```
### q_release_element
釋放特定節點的記憶體空間，包含節點裡儲存的 `value` 字串也一並釋放掉
```c
/*
* WARN: This is for external usage, don't modify it
* Attempt to release element.
*/
void q_release_element(element_t *e)
{
free(e->value);
free(e);
}
```
### q_size
計算目前佇列的節點總量，設定一個變數 `len`，初始值為 `0`，再使用 `list_for_each` 來遍歷佇列中的所有節點，每經過一個節點 `len` 就加一，最後回傳 `len` 的值，若佇列為 `NULL` 或 `empty` 則返回 `0`，
```c
/*
* Return number of elements in queue.
* Return 0 if q is NULL or empty
*/
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
移走佇列中間的節點，作法參考
>[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) 案例探討 : [Leetcode 2095. Delete the Middle Node of a Linked List](https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/)
原本的案例探討是針對單向的 linked list，我將其改為雙向環狀 linked list 的版本，若傳入的佇列為 `NULL` 或是空佇列，則回傳 `false`。
使用指標的指標，搭配快慢指標的技巧來找出中間的節點，首先設定一個指標的指標 `indir`，以及一個指標 `fast`，兩個指標都會指向 `head->next`，然後使用迴圈走訪節點，`fast` 每次會前進兩個節點，而 `indir` 每次前進一個，當 `fast` 本身等於 `head` 或是 `fast->next` 等於 `head` 時，代表已走訪完佇列，這時 `indir` 會指向佇列中間的節點。
找到中間節點後，使用 `list_entry` 來取得相對應的 `element_t`，然後用 `list_del` 及 `q_release_element` 來移除節點並釋放記憶體空間，最後回傳 `true`。
```c
/*
* 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.
*/
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 **indir = &head->next;
struct list_head *fast;
for (fast = head->next; (fast != head) && (fast->next != head);
fast = fast->next->next)
indir = &(*indir)->next;
element_t *del = list_entry(*indir, element_t, list);
list_del(*indir);
q_release_element(del);
return true;
}
```
### q_delete_dup
在已經排序的狀況，移走佇列中具備重複內容的節點，若傳入的佇列為 `NULL`，回傳 `false`。
>以下實作有參考 [laneser](https://hackmd.io/@laneser/linux2022_lab0#q_delete_mid) 同學的作法。
設定兩個 `element_t *` 變數 `cur`、`nex`，以及兩個 `struct list_head *` 變數 `curr`、`next`，初始化 `curr = head->next`、`next = head->next->next`，使用迴圈來走訪節點，在走訪的過程中使用 `list_entry` 來取得 `curr`、`next` 所對應的 entry `cur` 和 `nex`。
另外，在走訪節點的過程中需要考慮兩個情況：
1. `cur->value == nex->value`：
* 刪除 `cur`，並將 `needDel` 設成 `true`，表示所有與 `cur` 有相同字串的 entry 都是需要刪除的節點。
2. `cur->value != nex->value`：
* 若 `needDel == true` 表示 `cur` 也是需要刪除的 entry。
* 若 `needDel == false` 表示 `cur` 無須刪除。
```c
/*
* 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.
*/
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
if (!head)
return false;
bool needDel = false;
struct list_head *curr, *next;
element_t *cur = NULL, *nex = NULL;
for (curr = head->next, next = head->next->next; next != head;
curr = next, next = next->next) {
cur = list_entry(curr, element_t, list);
nex = list_entry(next, element_t, list);
if (strcasecmp(cur->value, nex->value) == 0) {
list_del(curr);
q_release_element(cur);
needDel = true;
} else if (needDel) {
list_del(curr);
q_release_element(cur);
needDel = false;
}
}
if (needDel) {
cur = list_entry(curr, element_t, list);
list_del(curr);
q_release_element(cur);
}
return true;
}
```
在走訪完所有節點後 `cur` 會指向佇列的最後一個節點，若此時 `needDel` 依然為 `true`，則代表佇列最後的兩個節點所包含的字串是相同的，兩個節點都需要刪除，而迴圈過程中會刪除倒數第二個節點，最後一個節點則需透過刪除 `cur` 來刪除。
### q_swap
交換佇列中鄰近的節點，若傳入的佇列為 `NULL`，則不做任何動作。
這個 `function` 中我主要是用 `list_move` 來完成實作：
```c
/* list_move API */
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
```
`list_move` 會將 `node` 移到佇列的開頭，也就是會讓 `head->next` 指向 `node`，利用這個功能，搭配迴圈走訪節點，一開始設定一個指標 `h` 指向 `head`。
每次迴圈 `h` 會前進兩個節點 `h = h->next->next`，將 `h->next->next` 當作新的 `head` 代入 `list_move` 中，就可達到交換佇列中鄰近的節點的目的。
```c
/*
* Attempt to 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 *h;
for (h = head; (h->next != head) && (h->next->next != head);
h = h->next->next)
list_move(h->next->next, h);
}
```
### q_reverse
以反向順序重新排列鏈結串列
```c
/*
* 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.
*/
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *swap = head->next;
struct list_head *stop = NULL;
while (stop != head) {
stop = swap->next;
list_move(swap, head);
swap = stop;
}
}
```
### q_sort
以==遞增順序==來排序鏈結串列的節點
#### list_append
```c
void list_append(struct list_head *list, struct list_head *head)
{
struct list_head *head_last = head->prev;
struct list_head *list_last = list->prev;
head_last->next = list;
list_last->next = head;
list->prev = head_last;
head->prev = list_last;
}
```
#### mergeTwoLists
```c
struct list_head *mergeTwoLists(struct list_head *L1, struct list_head *L2)
{
struct list_head *head;
struct list_head **ptr = &head;
do {
element_t *entryL1 = list_entry(L1, element_t, list);
element_t *entryL2 = list_entry(L2, element_t, list);
if (strcasecmp(entryL1->value, entryL2->value) < 0) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
list_del_init(*ptr);
list_add_tail(*ptr, head);
ptr = &(*ptr)->next;
} while ((L1->next != head) && (L2->next != head));
L1->next == head ? list_append(L2, head) : list_append(L1, head);
return head;
}
```
#### mergesort_list
```c
struct list_head *mergesort_list(struct list_head *entryHead)
{
if (entryHead->next == entryHead && entryHead->prev == entryHead)
return entryHead;
struct list_head *entryTail = entryHead->prev;
struct list_head *slow = entryHead, *fast;
for (fast = entryHead->next;
(fast != entryHead) && (fast->next != entryHead);
fast = fast->next->next)
slow = slow->next;
struct list_head *mid = slow->next;
mid->prev = entryTail;
entryTail->next = mid;
slow->next = entryHead;
entryHead->prev = slow;
struct list_head *left = mergesort_list(entryHead);
struct list_head *right = mergesort_list(mid);
return mergeTwoLists(left, right);
}
```
#### q_sort
```c
/*
* 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.
*/
void q_sort(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *entryHead = head->next;
list_del_init(head);
struct list_head *sorted = mergesort_list(entryHead);
list_append(sorted, head);
}
```
Sign in with Wallet
Connect another wallet