# 2023q1 Homework1 (lab0)
contributed by < `qiaoyi213` >
:::danger
注意項目符號的使用，標題用 ==`# `== 開頭，分項就該以 ==`## `== 開頭，並該維護階層關係。
登記在 https://hackmd.io/@sysprog/linux2023-homework1 的網址，要用「固定網址」(參見 用固定網址發布筆記)，也就是如 https://hackmd.io/@itsme/XXXX 的形式，設定公開發表。
:notes: jserv
:::
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 12.2.0-3ubuntu1) 12.2.0
$ lscpu
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Vendor ID: 0x00
Model name: -
Model: 0
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
Stepping: 0x0
BogoMIPS: 48.00
```
[作業敘述與要求](https://hackmd.io/@sysprog/linux2023-lab0)
:::danger
不用抄題目，善用超連結。
:notes: jserv
:::
:::spoiler 進度表
- [x] `q_new`
- [x] `q_free`
- [x] `q_insert_head`
- [x] `q_insert_tail`
- [x] `q_remove_head`
- [x] `q_remove_tail`
- [x] `q_size`
- [x] `q_delete_mid`
- [x] `q_delete_dup`
- [x] `q_swap`
- [x] `q_reverse`
- [x] `q_reverseK`
- [x] `q_sort`
- [x] `q_descend`
- [x] `q_merge`
:::
## 閱讀 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
### indirect pointer
一開始並不懂 indirect pointer 的用意，看了許久還是不理解為什麼這麼做。
:::danger
看不懂就該列出教材哪裡沒寫好。不要說「大概懂」，無法應用和指出如何改進就是不懂。
:notes: jserv
:::
參考 [Mes 的筆記](
https://hackmd.io/@Mes/mes_note/https%3A%2F%2Fhackmd.io%2F%40Mes%2FThe_mind_behind_Linux) 後就大概懂 indirect pointer 的技巧，但在實作上可能還需要熟悉。
## 常用結構與巨集
寫到一半發現真的對我自己寫的東西很不確定，所以回來重新審視 `queue.h` 以及 `list.h`。
:::warning
幻滅是成長的開始。
:notes: jserv
:::
### list_head
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
### element_t
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
## 開發過程
### Null pointer deference
:::warning
在執行下列命令時
```shell
$cppcheck queue.c
```
多次出現 `Null pointer deference` 的錯誤，目前還不知道怎麼解決。
例如：
>queue.c:71:22: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *tmp = list_first_entry(head, element_t, list);
:::
## 實作 queue.[ch]
### `q_new`
參考 `list.h` 中的 `INIT_LIST_HEAD` 函式，此函式是將 `linked list` 中的 `prev` 指標以及 `next` 指標指向自己，形成一個環形的 `linked list`。
```c
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
```c
struct list_head *q_new()
{
struct list_head *li = malloc(sizeof(struct list_head));
if(li)
INIT_LIST_HEAD(li)
return li;
}
```
### `q_free`
從頭開始依序迭代所有的節點，移除該節點後就釋放該節點記憶體。
利用 `list.h` 中的巨集 `list_for_each_entry_safe` 實作 `q_free`。
:::danger
注意[資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:notes: jserv
:::
:::success
已將「遍歷」修正為「迭代」
:::
```c
void q_free(struct list_head *l)
{
element_t *entry, *safe;
list_for_each_entry_safe(entry, safe, l, list)
q_release_element(entry);
free(l);
}
```
### `q_insert_head`
使用 `list_add` 巨集新增節點
```c
bool q_insert_head(struct list_head *head, char *s)
{
if(!head)
return false;
element_t *new = malloc(sizeof(element_t));
if(!new)
return false;
new->value = strdup(s);
if(!new->value) {
free(new);
return false;
}
list_add(&new->list, head);
return true;
}
```
### `q_insert_tail`
與 `q_insert_head` 實作方法相似，只是將 `list_add()` 更換為 `list_add_tail()`
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *new = malloc(sizeof(element_t));
if (!new)
return false;
new->value = strdup(s);
if (!new->value) {
free(new);
return false;
}
list_add_tail(&new->list, head);
return true;
}
```
### `q_size`
遍歷所有節點並且記錄 `linked list` 的大小。
```c
int q_size(struct list_head *head)
{
if(!head)
return 0;
int size = 0;
struct list_head *node;
list_for_each(node, head)
size++;
return size;
}
```
### `q_remove_head`
:::warning
目前測試結果仍有錯誤：Probably not constant time or wrong implementation
:::
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if(!head || list_empty(head))
return NULL;
element_t *tmp = list_entry(head->next, element_t, list);
if(sp){
strncpy(sp, tmp->value, bufsize-1);
sp[bufsize-1] = '\0';
}
list_del(&tmp->list);
return tmp;
}
```
### `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 *tmp = list_entry(head->prev, element_t, list);
if(sp){
strncpy(sp, tmp->value, bufsize-1);
sp[bufsize-1] = '\0';
}
list_del(&tmp->list);
return tmp;
}
```
### `q_delete_mid`
使用 `slow` 指標以及 `fast` 指標
每次移動 `slow` 指標一次、`fast` 指標兩次，即可找到中間的位置。
```c
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 *fast, *slow;
slow = head->next;
fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
list_del(slow);
element_t *e = list_entry(fast, element_t, list);
list_del(fast);
free(e->value);
free(e);
return true;
}
```
### `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;
if(list_empty(head) || list_is_singular(head))
return true;
bool is_dup = false;
element_t *node, *safe;
list_for_each_entry_safe(node, safe, head, list){
if(&safe->list != head && strcmp(node->value, safe->value) == false){
list_del(&node->list);
q_release_element(node);
is_dup = true;
} else if ( is_dup ){
list_del(&node->list);
q_release_element(node);
is_dup = false;
}
}
return true;
}
```
### `q_reverse`
```c
void q_reverse(struct list_head *head)
{
if(!head || list_empty(head))
return;
struct list_head *node, *safe;
list_for_each_safe(node, safe, head)
list_move(node,head);
return;
}
```
### `q_reverseK`
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if(!head || list_empty(head) || k < 2)
return;
int list_length = q_size(head);
for(struct list_head *now = head->next;now != head && now->next != head;now = now->next) {
struct list_head **curr = &now->next, *tmp = now->prev;
for(int i=1;i<k;i++)
if(list_length >= k)
list_move(*curr, tmp);
}
}
```
### `q_swap`
```c
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;
for(struct list_head *curr = head->next; curr != head && curr->next != head; curr = curr->next)
list_move(curr, curr->next);
}
```
### `merge_two_list`
參考 [你所不知道的 C 語言: linked list 和非連續記憶體](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) 後重新實作一遍。
將兩個已排序好的 `linked list` 合併並排序。
:::warning
疑惑：在原本的範例中是使用 `uintptr_t`，我不清楚為什麼這裡是使用 `u_int64_t` 才對。
:::
```c
struct list_head *merge_two_list(struct list_head *l1, struct list_head *l2)
{
struct list_head *head, **ptr, **node;
head = NULL;
ptr = &head;
for(node = NULL; l1 && l2; *node=(*node)->next){
if(strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) < 0)
node = &l1;
else
node = &l2;
*ptr = *node;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);
return head;
}
```
### `merge_sort`
實作 merge sort，並且使用與 `q_delete_mid` 相同的方法找位於 `queue` 中間的節點以分治。
```c
static inline struct list_head merge_sort(struct list_head *head)
{
if(!head || !head->next)
return head;
struct list_head *fast, *slow;
fast = head->next;
slow = head->next;
while (slow != fast && slow->next != fast) {
slow = slow->next;
fast = fast->next->next;
}
struct list_head *left, *right;
right = slow->next;
slow->next = NULL;
left = merge_sort(head);
right = merge_sort(right);
return merge_list(left, right);
}
```
### `q_sort`
首先要先將 `linked list` 斷開連接變成 `singular linked list` 之後進行 merge sort 之後再重新連接。
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
head->prev->next = NULL;
head->next = mergesort(head->next);
struct list_head *current = head, *next = head->next;
while (next) {
next->prev = current;
current = next;
next = next->next;
}
current->next = head;
head->prev = current;
}
```
## `q_merge`
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (!head || list_empty(head))
return 0;
if (list_is_singular(head))
return q_size(list_first_entry(head, queue_contex_t, chain)->q);
int queue_size = 0;
queue_contex_t *first, *second;
first = list_first_entry(head, queue_contex_t, chain),
second = list_entry(first->chain.next, queue_contex_t, chain);
while (second->q) {
queue_size = q_size(merge_two_list(first->q, second->q));
second->q = NULL;
list_move_tail(&second->chain, head);
second = list_entry(first->chain.next, queue_contex_t, chain);
}
return queue_size;
}
```
### `q_descend`
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
element_t *entry;
list_for_each_entry (entry, head, list) {
struct list_head *prev = entry->list.prev, *safe = prev->prev;
for (; prev != head; prev = safe, safe = safe->prev) {
element_t *prev_entry = list_entry(prev, element_t, list);
if (strcmp(prev_entry->value, entry->value) >= 0)
break;
list_del(prev);
q_release_element(prev_entry);
}
}
return 0;
}
```
:::info
`make test` 分數：71/100
:::
Sign in with Wallet
Connect another wallet