# 2023q1 Homework1 (lab0)
contributed by < `chiacyu` >
### 開發環境
```bash
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
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-4720HQ CPU @ 2.60GHz
Stepping: 3
CPU MHz: 1700.000
CPU max MHz: 3600.0000
CPU min MHz: 800.0000
BogoMIPS: 5187.53
Virtualization: VT-x
L1d cache: 128 KiB
L1i cache: 128 KiB
L2 cache: 1 MiB
L3 cache: 6 MiB
NUMA node0 CPU(s): 0-7
```
## 開發日誌
:::success
做作業前可以先研讀 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)對於實作過程大有幫助。
:::
### q_new
這邊需要注意的部份在根據 `malloc` 的說明:
> On error, these functions return NULL.
若是失敗時會回傳 `NULL` 因此就算失敗也必須要使用 `free` 來釋放記憶體。
```c
struct list_head *q_new()
{
struct list_head *q_head = malloc(sizeof(struct list_head));
if (!q_head) {
free(q_head);
return NULL;
}
INIT_LIST_HEAD(q_head);
return q_head;
}
```
### q_free()
釋放記憶體的部份則是透過 `list_for_entry_safe` 依序走訪過每一個 `element` 來釋放每個節點所佔用的記憶體。
```c
void q_free(struct list_head *l)
{
if (!l) {
return;
}
if (list_empty(l)) {
free(l);
}
element_t *entry, *safe;
list_for_each_entry_safe (entry, safe, l, list) {
if (entry->value) {
free(entry->value);
}
free(entry);
}
free(l);
return;
}
```
### q_insert_head()
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
free(q);
return false;
}
q->value = strdup(s);
list_add(&q->list, head);
return true;
}
```
### q_insert_tail()
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head) {
return false;
}
element_t *q = malloc(sizeof(element_t));
if (!q) {
free(q);
return false;
}
q->value = strdup(s);
list_add_tail(&q->list, head);
return true;
}
```
### 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 *q_head = list_first_entry(head, element_t, list);
list_del(&q_head->list);
if (!q_head) {
free(q_head);
return NULL;
}
strncpy(sp, q_head->value, bufsize);
return q_head;
}
```
### q_remove_tail()
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
element_t *q_tail;
q_tail = list_last_entry(head, element_t, list);
list_del(&q_tail->list);
if (!q_tail){
free(q_tail);
return NULL;
}
strncpy(sp, q_tail->value, bufsize);
return q_tail;
}
```
:::warning
思考如何縮減程式碼。
:notes: jserv
:::
### 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()
這邊用的方式是先計算出 `queue` 的長度，再取下高斯的方式來找出 `mid` 的位置
:::danger
改進漢語描述，並描述對應的演算法。
:notes: jserv
:::
```c
bool q_delete_mid(struct list_head *head)
{
if (!head){
return false;
}
int q_num = q_size(head);
q_num = q_num/2;
struct list_head *mid = head;
while (q_num--) {
mid = mid->next;
}
element_t *mid_node = list_entry(mid, element_t, list);
list_del(&mid_node->list);
// https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
return true;
}
```
### q_delete_dup()
`delete` 的方式用兩個指標 先去若是遇到重複的字串 將第二個指標持續往 `next` 前進直到不同 再第一個指標往 `next` 走得過程刪除重複的節點
:::warning
改進漢語表達。
:notes: jserv
:::
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL) {
return false;
}
struct list_head *curr = head->next, *nextt;
bool dup_flag = false;
while (curr && curr->next) {
if (curr == head || curr->next == head)
break;
nextt = curr->next;
element_t *node_f = list_entry(curr, element_t, list);
element_t *node_s = list_entry(nextt, element_t, list);
while (strcmp(node_f->value, node_s->value) == 0) {
nextt = nextt->next;
if (nextt == head) {
break;
}
node_s = list_entry(nextt, element_t, list);
dup_flag = true;
}
if (dup_flag) {
while (curr != nextt) {
struct list_head *delete_node = curr;
curr = curr->next;
list_del(delete_node);
free(list_entry(delete_node, element_t, list));
}
dup_flag = false;
}
curr = curr->next;
}
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
return true;
}
```
### q_swap()
`swap` 的實作方式則是用兩個指標分別指到，欲插入頭部的位置與欲移動節點之位置。由於後一個節點的 `next` 會指向 `head` 因此可以作為判斷之條件來檢視是否走遍所有節點。
```c
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head *node = head->next;
while (node && node->next) {
struct list_head *next_n;
if (node == head || node->next == head)
break;
next_n = node->next;
list_del(node);
list_add(node, next_n);
node = node->next;
}
return;
// https://leetcode.com/problems/swap-nodes-in-pairs/
}
```
### q_reverse()
```c
void q_reverse(struct list_head *head)
{
if (list_empty(head)) {
return;
}
struct list_head *node, *safe;
list_for_each_safe (node, safe, head) {
list_move(node, head);
}
return;
}
```
### q_reverseK()
目前的實作方式是用兩個指標，第一個指標放在 `前頭` ，第二個指標指向欲移動的點。但目前這種方式當遇到 `queue` 長度能被 `k` 整除時會有問題，需要再改進。
```c
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (list_empty(head) || k < 2) {
return;
}
int reverse_count = q_size(head)/ k;
int interval = k - 1;
struct list_head *start = head->next, *end = head->next;
while (reverse_count--) {
while (interval--) {
end = end->next;
}
while (end != start) {
struct list_head *move_node = end;
end = end->prev;
list_del(move_node);
list_add_tail(move_node, start);
}
start = start->next;
end = start;
if(start == head || start->next== head) break;
}
return;
}
```
### q_sort()
目前是依照 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 內文提供的遞迴版本去實作。 唯一的差別是在與這邊的實作是取 `first entry` 作為 `pivot` ，範例的版本則是取最後一個 `entry` 作為 `pivot` 。 原本在宣告 `large_head` 跟 `small_head` 的時候是使用 `malloc` 但發現在執行時期會發生 `FATAL ERROR: Calls to malloc disallowed` 後來才改為不需要 `malloc` 的版本。
```c
void q_sort(struct list_head *head) {
if (list_empty(head) || list_is_singular(head)){
return;
}
struct list_head large_head;
struct list_head small_head;
element_t *pivot_node;
element_t *current_node;
element_t *safe;
INIT_LIST_HEAD(&large_head);
INIT_LIST_HEAD(&small_head);
pivot_node = list_last_entry(head, element_t, list);
list_del(&pivot_node->list);
list_for_each_entry_safe(current_node, safe, head, list){
if(strcmp(current_node->value, pivot_node->value) < 0){
list_move_tail(¤t_node->list, &small_head);
}
else if(strcmp(current_node->value, pivot_node->value) >= 0){
list_move_tail(¤t_node->list, &large_head);
}
}
q_sort(&large_head);
q_sort(&small_head);
list_add(&pivot_node->list, head);
list_splice(&small_head, head);
list_splice_tail(&large_head, head);
}
```
### q_descend
```c
int q_descend(struct list_head *head)
{
// https://leetcode.com/problems/remove-nodes-from-linked-list/
if (!head || list_empty(head)) {
return 0;
}
struct list_head *curr = head->prev;
struct list_head *safe = head->prev;
char *max_value = '\0';
int count_size = 0;
while (curr != head) {
curr = safe;
safe = curr->prev;
count_size+=1;
element_t *entry = list_entry(curr, element_t, list);
if (strcmp(entry->value, max_value) > 0) {
max_value = strdup(entry->value);
} else {
list_del(curr);
free(entry);
count_size+=1;
}
}
return count_size;
}
```
### q_merge()
這邊的作法是透過，`list_for_each_entry_safe` 的方式將每一個節點走遍。 假設總共有三個 `queue` `[A,B,C]` `[D,E,F]` `[G,H,I]`, 先準備一個 `sort_head` 並將所有節點移動至此成 `[A,B,C,D,E,F,G,H,I]` 此時三個佇列變成 `[]` `[]` `[]`，在將 `sort_head` 排序後串回第一個 `queue`, 變成 `[A,B,C,D,E,F,G,H,I]` `[]` `[]` 。
```c
int q_merge(struct list_head *head)
{
// https://leetcode.com/problems/merge-k-sorted-lists/
if (list_empty(head)) {
return 0;
}
int count = 0;
struct list_head sort_head;
INIT_LIST_HEAD(&sort_head);
queue_contex_t *itr;
queue_contex_t *itr_safe;
list_for_each_entry_safe (itr, itr_safe, head, chain) {
count += itr->size;
list_splice_init(itr->q, &sort_head);
}
q_sort(&sort_head);
list_splice_init(&sort_head, list_first_entry(head, queue_contex_t, chain)->q);
printf("The count is %d\n", count);
return count;
}
```
## 網頁伺服器
## Shuffle 實作
Sign in with Wallet
Connect another wallet