owned this note
owned this note
Published
Linked with GitHub
# 2025q1 Homework1 (lab0)
> contributed by < [ginsengAttack](https://https://github.com/) >
### Reviewed by `HeatCrab`
程式碼的異同可以善用 diff 來顯示，像是 q_merge 的實作，就不必貼出兩次如此冗長的程式碼，可讀性很差。
原本是：
>此時的程式碼：
> ```c
> if (!head || head->next == head)
> return 0;
> ...
> ```
更改為：
```diff
if (!head || head->next == head)
return 0;
else if (head->next->next == head)
- return q_size(list_entry(head->next,queue_contex_t,chain)->q);
+ return list_entry(head->next,queue_contex_t,chain)->size;
int num = q_size(head);
int firstPos = 0;
+ int totalSize = 0;
struct list_head *first = NULL;
struct list_head *tail;
for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
- if (list_entry(pos,queue_contex_t,chain)->q->next != list_entry(pos,queue_contex_t,chain)->q) {
+ if (list_entry(pos,queue_contex_t,chain)->size != 0) {
first = list_entry(pos,queue_contex_t,chain)->q->next;
+ totalSize = list_entry(pos,queue_contex_t,chain)->size;
list_del(list_entry(pos,queue_contex_t,chain)->q);
+ tail = pos->next;
if (pos != head->next) //this 2
list_entry(pos,queue_contex_t,chain)->q = NULL;
break;
}else if (pos != head->next)
list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
firstPos++;
}
if (!first || firstPos == num)
return 0;
- tail = first->next;
for (int i = firstPos+1;i < num; i++) {
- if (list_entry(tail,queue_contex_t,chain)->q->next == list_entry(tail,queue_contex_t,chain)->q) {
+ if (list_entry(tail,queue_contex_t,chain)->size == 0) {
list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
continue;
}
struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
list_del(list_entry(tail,queue_contex_t,chain)->q);
list_entry(tail,queue_contex_t,chain)->q = NULL;
+ totalSize += list_entry(tail,queue_contex_t,chain)->size;
+ list_entry(tail,queue_contex_t,chain)->size = 0;
first = merge_two(first,link);
tail = tail->next;
}
list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
if (descend)
q_reverse(head);
- return q_size(list_entry(head->next,queue_contex_t,chain)->q);//this 5
+ list_entry(head->next,queue_contex_t,chain)->size = totalSize;
return totalSize;//this 5
```
這樣可以更直觀的顯示出程式碼的改變。另外也可以附上 commit 紀錄，就可以不用張貼程式碼，github 也有內建的 diff 方便檢閱與 code review ！
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
架構： x86_64
CPU 作業模式： 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
字節序： Little Endian
CPU: 16
CPU 列表： 0-15
供應商識別號： GenuineIntel
型號名稱： Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz
CPU 家族： 6
型號： 165
每核心執行緒數： 2
每通訊端核心數： 8
座： 1
製程： 5
CPU(s) scaling MHz: 23%
CPU 最大 MHz： 4800.0000
CPU 最小 MHz： 800.0000
BogoMIPS： 5799.77
Virtualization features:
虛擬： VT-x
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 2 MiB (8 instances)
L3: 16 MiB (1 instance)
NUMA:
NUMA 節點： 1
NUMA node0 CPU(s)： 0-15
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Reg file data sampling: Not affected
Retbleed: Mitigation; Enhanced IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prct
l
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointe
r sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditiona
l; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop,
KVM SW loop
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
## 程式碼部份：
### q_new
一開始我寫：
```c
struct list_head *head=malloc(sizeof(struct list_head));
INIT_LIST_HEAD(head);
element_t *node=malloc(sizeof(element_t));
node->list=*head;
return &node->list;
```
思路是因為我記得在小考的時候有看過， linux核心的鏈節串列結構比較特別，是將 list_head嵌入結構當中，所以我想先建立一個 list_head的指標，然後再把它嵌入到 element_t當中。
```c
element_t *node = malloc(sizeof(element_t));
if (!node)
return NULL;
INIT_LIST_HEAD(&node->list);
return &node->list;
```
後來我想到，只要我建立一個 element_t的空間，裡面自然有一個區塊是用來存 list_head的結構。
```c
element_t *node = malloc(sizeof(element_t));
if (node)
INIT_LIST_HEAD(&node->list);
return &node->list;
```
然後過程中，一開始我的指標是指向 NULL，查看 queue.h 才知道具體格式，上述的程式碼是在同學建議下簡化的
有些網路上的寫法（同學看的），這邊都直接創立一個 list_head 節點而已，我覺得這是不太對的，這樣子佇列就只是無意義串接的鍊結串列而已，連存值的地方都沒有。
```c
struct list_head *new = malloc(sizeof(struct list_head));
INIT_LIST_HEAD(new);
return new;
```
搞錯了，我自作聰明，第一個指標不需要存值。
### q_free
嘗試：
```c
if (head) {
struct list_head *del = NULL;
struct list_head *pos;
for(pos = head->next; pos!=head ; pos=pos->next){
if (del)
free(list_entry(del,element_t,list));
del=pos;
}
}
if (head)
free(list_entry(head,element_t,list));
```
我知道要用 list_for_each 系列寫，先用熟悉的方法嘗試看看邏輯
目前看來是可以運行的，但是因為只有創建單個元素的節點，所以還不能完全確定是完善的。
```c
struct list_head *pos = head->next;
while (pos != head) {
pos = head->next;
list_del(pos);
element_t *node = list_entry(pos, element_t, list);
free(node);
}
free(head);
```
這邊我發現自己對 head 的理解有問題，所以更新了一下程式碼，把想要刪除的節點先從佇列 "remove" 掉，然後再釋放記憶體空間。
結果顯示我還有空間未釋放，這邊我剛剛更新了 insert 的程式碼，所以我記得我有特別幫新節點的字串分配空間，如果釋放節點的空間，我只會將其中的 list head 和 "指向 string 的指標"刪除， string 本身還會存在，所以我也要先刪除 string 本身。
我在進行 new 測試的時候一直有問題，而且問題是出在釋放記憶體空間的時候，後來發現是沒有檢測 head 是否為空:
```c
if (!head)
return;
```
### q_insert_head
```c
element_t *node = malloc(sizeof(element_t));
node->value = s;
(node->list).next = *head;
(node->list).prev = (*head)->prev;
(*head)->prev = &node->list;
*head = &node->list;
if (!node)
return false;
else
return true;
```
程式碼有誤，但是我還沒想明白怎更改 head 的位置，我直覺傳入的參數應該要是 list_head** 但不能修改這邊，所以之後再想想看辦法。
```c
element_t *node = malloc(sizeof(element_t));
node->value = s;
list_add(&node->list,head);
return true;
```
我明白我錯哪裡了，跟剛剛前面 queue new 遇到的問題一樣，是加在 head 的後面。
但還是會遇到問題：
```
ERROR: Need to allocate and copy string for new queue element
```
我想過要先分配新空間，但是還是有一樣的狀況，最後發現問題出在對字串指標的處理，因為我直接指向傳入參數 s 的話，就沒有幫節點新增空間，所以最終使用 strdup 分配新空間給字串就好：
```c
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
node->value = strdup(s);
list_add(&node->list,head);
return true;
```
最終測試有問題，看測試命令應該是故意讓記憶體的配置出錯，所以我重點關注記憶體配置出錯的處理， strdup 本身也是記憶體分配的函式所以不能忽視。
最終是在同學提示下我才找到真正的問題點，我配置 element_t 失誤的話回傳 false 當然就沒問題，但是如果是在配置 node value 的時候失誤， element_t 卻還會存在，必須釋放。
```c
if (!node->value) {
free(node);
return false;
}
```
### q_insert_tail
```c
element_t *tail = malloc(sizeof(element_t));
tail->value = s;
head->prev->next = &tail->list;
(tail->list).prev = head->prev;
head->prev = &tail->list;
(tail->list).next = head;
return true;
```
一開始我先用自己的方式寫，但是只有在加入第一個節點的時候不會有問題，所以我改用提供的 API 實做看看：
```c
element_t *tail = malloc(sizeof(element_t));
tail->value = s;
list_add_tail(&tail->list,head);
return true;
```
還是有錯，問題和前一個相同，不贅述：
```c
if (!head)
return false;
element_t *node = malloc(sizeof(element_t));
node->value = strdup(s);
list_add_tail(&node->list, head);
return true;
```
### q_remove_head
```c
struct list_head *pos = NULL;
for (pos = head->next;pos != head;pos=pos->next) {
if (strncmp(list_entry(pos,element_t,list)->value,sp,bufsize) == 0){
list_del(pos);
free(list_entry(pos,element_t,list)->value);
free(list_entry(pos,element_t,list));
}
}
return NULL;
```
一開始看不太懂，想說就是刪掉字串為 sp 的節點，不懂要回傳啥，感覺有點矛盾，但是他是說 "remove" ，好像跟回傳值不衝突，而且要回傳是 node ，同時不用釋放節點才對：
```c
if (!head || head->next == head)
return NULL;
element_t *node = list_entry(head->next, element_t, list);
strncpy(sp, node->value, bufsize);
list_del(&node->list);
return node;
```
這邊寫的時候還有遇到 string copy 的用法錯誤、忘記刪除節點。
後來測試的時候出現錯誤，錯誤大概是指要刪除的字串是 apple ，但讀到的卻是 apple_xxxxxx... 很明顯是結束字元的問題， strncopy 沒辦法把結束字元也複製，所以把 buffsize 減去一，然後手動在最後加上 '\0':
```c
strncpy(sp, node->value, bufsize - 1);
sp[bufsize - 1] = '\0';
```
### q_delete_mid
我有寫過這題 leetcode :
用指標的指標完成的，但是這個函數的部份好像用不到這個技巧，所以我直接寫：
```c
struct list_head *slow = head->next;
const struct list_head *pos;
for (pos = head->next; pos->next != head && pos->next->next != head;
pos = pos->next->next)
slow = slow->next;
list_del(slow);
free(list_entry(slow, element_t, list)->value);
free(list_entry(slow, element_t, list));
return true;
```
沒啥難度，用快慢指標，快的走兩步慢的走一步，當快的走到盡頭慢的自然走到一半。
好像也可以用一個往前一個往右的方式寫，但是速度應該不會比較快，所以不改。
### q_swap
```c
struct list_head **cur = &head->next;
struct list_head *nex;
for (; *cur != head && (*cur)->next != head; cur = &(*cur)->next->next) {
nex = (*cur)->next;
(*cur)->next = nex->next;
nex->next = *cur;
nex->prev = (*cur)->prev;
(*cur)->prev = nex;
*cur = nex;
}
```
這題我用間接指標實做，讓 current 和 next 兩個指標做交換，接著 current 往後兩步。
我還有想到一個方法，就是把一個節點先 remove 後，再把它加入到後面，可以直接通過調取 API 來實現這段程式碼，但是也沒有比較快。
測試結果有誤，看了很久沒想到是 swap 的問題，然後仔細看了一下，發現是向前指標出錯了，假設我要將1.2.3三個節點做 swap，我的3沒有把 prev 改成1。
```c
nex->next->prev = *cur;
```
加在迴圈內的第三行。
### q_reverse
```c
struct list_head *first = head->next;
list_move_tail(first,head);
for (struct list_head *pos = head->next;pos != first;){
list_move_tail(pos,head);
pos = head->next;
}
```
想說把每個節點丟到最後面，結果輸出的佇列完全沒變，才發現邏輯有錯，應該是從最後一個節點開始把所有的節點依序丟到最後，或者乾脆改從第一個節點開始把節點一須丟到最前面:
```c
struct list_head *cur = head->next,*nex;
for(nex = cur->next;cur != head;) {
list_move(cur,head);
cur = nex;
nex = cur->next;
}
```
### q_sort
我先試著使用泡沫排序來實做，參考整數的排序法：
```c
for(int i=0;i<sort.size();i++){
for(int j=0;j<sort.size()-1;j++){
if(sort[j]>sort[j+1])
swap(sort[j],sort[j+1]);
}
}
```
這邊要考慮到，我是 j 和 j+1 做交換，所以要注意範圍，一開始就是這部份沒注意到所以出錯了，然後我使用 list move 實做出：
```c
for (int i=0;i<q_size(head)+1;i++){
for(struct list_head *pos=head->next;pos->next != head;){
if (list_entry(pos,element_t,list)->value > list_entry(pos->next,element_t,list)->value) {
list_move(pos->next,pos);
}else
pos = pos->next;
}
}
```
很明顯我誤會 list move的用法了，把它當成純粹的 swap 在用，所以我這段操作完全沒意義，所以我又修改：
```c
for (int i=0;i<q_size(head);i++){
for(struct list_head *pos=head->next;pos->next != head;){
if (list_entry(pos,element_t,list)->value > list_entry(pos->next,element_t,list)->value)
list_move(pos,pos->next);
else
pos = pos->next;
}
}
```
我一開始以為 move 功能是把 node 加到 head 前面，所以寫 list_move(pos,pos->next) ，又發現前面的參數才是 node 所以改成相反，然後又發現他是將 node 加到 head之後，所以 pos->next 才是 head ，又改相反。
但是測試的時候發現一直有問題，最後知道是字串比較的部份出錯，所以改用 strcmp 解決：
```c
for (int i=0;i<q_size(head);i++){
for(struct list_head *pos=head->next;pos->next != head;){
if (strcmp(list_entry(pos,element_t,list)->value,list_entry(pos->next,element_t,list)->value)>0)
list_move(pos,pos->next);
else
pos = pos->next;
}
}
```
之後改成 merge sort:
```c
void q_sort(struct list_head *head, bool descend)
{
struct list_head *list = head->next;
list_del(head);
list = merge_sort(list);
list_add_tail(head,list);
}
```
```c
struct list_head* merge_sort(struct list_head *head)
{
int len = q_size(head);
if (len<=1) {
if (len == 0)
return head;
else if (strcmp(list_entry(head, element_t, list)->value,
list_entry(head->next, element_t, list)->value) > 0) {
list_move(head,head->next);
return head->next;
}
return head;
}
struct list_head *list1 = head;
struct list_head *list2 = head;
for (int i = len / 2; i >= 0; i--)
list2 = list2->next;
struct list_head *tmp = list2->prev;
list2->prev = list1->prev;
list1->prev = tmp;
list1->prev->next = list1;
list2->prev->next = list2;
list1 = merge_sort(list1);
list2 = merge_sort(list2);
struct list_head *trace1 = list1;
struct list_head *trace2 = list2;
bool list1_bool = false,list2_bool = false;
head = strcmp(list_entry(list1,element_t,list)->value,
list_entry(list2,element_t,list)->value) < 0 ? list1:list2;
do {
if (trace1 == head && list1_bool) {
struct list_head *tmp = trace2;
trace2 = trace2->next;
list_add_tail(tmp, trace1);
list2_bool = true;
}else if (strcmp(list_entry(trace1, element_t, list)->value,
list_entry(trace2, element_t, list)->value) <= 0) {
trace1 = trace1->next;
list1_bool = true;
}else {
struct list_head *tmp = trace2;
trace2 = trace2->next;
list_add_tail(tmp, trace1);
list2_bool = true;
}
}while(trace2 != list2 || !list2_bool);
return head;
}
```
程式有點亂，會想辦法精簡。
程式碼的判斷有問題，我將佇列分割成兩段之後，會選擇兩個新佇列首個元素最小的作為 head ，既是回傳值，又是走訪第一個佇列的中止條件，但是如果兩個佇列首元素一樣大，我一開始會優先把第二個佇列的首元素設置成 head，但是後續把兩個佇列合併的時候，我卻會優先把佇列一的元素放入合併完成的佇列。
這樣首元素一樣大的時候，我會把佇列二的首元素設置成 head 實際上的 head 卻是佇列一的。
再次精簡程式碼， merge_two ：
```c
void merge_two(struct list_head *list1, struct list_head *list2)
{
struct list_head *list1_pos = list1->next;
for (struct list_head *pos = list2->next;pos != list2 ;) {
if (list1_pos != list1 && strcmp(list_entry(list1_pos,element_t,list)->value,list_entry(pos,element_t,list)->value) < 0)
list1_pos = list1_pos->next;
else {
struct list_head *add = pos;
pos = pos->next;
list_del(add);
list_add_tail(add,list1_pos);
}
}
}
```
```c
if (!head || list_empty(head) || head->next->next == head)
return;
struct list_head *list2 = head;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
list2 = list2->next;
fast = fast->next->next;
}
struct list_head left;
list_cut_position(&left, head, list2);
q_sort(head,descend);
q_sort(&left,descend);
merge_two(head,&left);
```
改成用上面兩段就可以清楚的達到要求。
### q_delete_dup
```c
if (!head || head->next == head)
return false;
q_sort(head,false);
struct list_head **cur = &head->next;
while ((*cur)->next != head && *cur != head){
if(strcmp(list_entry(*cur,element_t,list)->value,list_entry((*cur)->next,element_t,list)->value) == 0){
struct list_head *tmp = (*cur)->next;
while (tmp != head && strcmp(list_entry(tmp,element_t,list)->value,list_entry(*cur,element_t,list)->value) == 0)
tmp = tmp->next;
*cur = tmp;
} else
cur = &(*cur)->next;
}
return true;
```
輸出結果正確，但是顯示錯誤，我推測是因為沒釋放記憶體？或是指標沒處理好？
```c
if (!head || head->next == head)
return false;
q_sort(head, false);
struct list_head **cur = &head->next;
while ((*cur)->next != head && *cur != head) {
if (strcmp(list_entry(*cur, element_t, list)->value,
list_entry((*cur)->next, element_t, list)->value) == 0) {
struct list_head *tmp = (*cur)->next;
while (tmp != head &&
strcmp(list_entry(tmp, element_t, list)->value,
list_entry(*cur, element_t, list)->value) == 0) {
struct list_head *del = tmp;
tmp = tmp->next;
list_del(del);
free(list_entry(del, element_t, list)->value);
free(list_entry(del, element_t, list));
}
struct list_head *del = *cur;
tmp->prev = (*cur)->prev;
*cur = tmp;
free(list_entry(del, element_t, list)->value);
free(list_entry(del, element_t, list));
} else
cur = &(*cur)->next;
}
return true;
```
我稍微調整了一下，但還是有錯。
有人說我的程式碼很醜，待改。
### q_ascend
這題沒啥難度， leetcode 很快就解出來了，但是實做一直有問題：
```c
if (!head || list_empty(head))
return 0;
int number = 1;
char *s = list_entry(head->prev, element_t, list)->value;
for (struct list_head *pos = head->prev; pos != head; pos = pos->prev) {
if (strcmp(s, list_entry(pos, element_t, list)->value) < 0)
list_del(pos);
else {
s = list_entry(pos, element_t, list)->value;
number++;
}
}
return number;
```
主要問題是出在 list_del 那行，參考函式內部邏輯：
```c
#ifdef LIST_POISONING
node->next = NULL;
node->prev = NULL;
#endif
```
我本來以為受刪除節點的 next 跟 prev 還會串接在原處，所以沒有進行特別的處理，導致發生問題，然後同時還必須把刪除的節點空間釋放掉：
```c
if (!head || list_empty(head))
return 0;
int number = 0;
char *s = list_entry(head->prev, element_t, list)->value;
for (struct list_head *pos = head->prev; pos != head;) {
if (strcmp(s, list_entry(pos, element_t, list)->value) < 0) {
struct list_head *del = pos;
pos = pos->prev;
list_del(del);
free(list_entry(del,element_t,list)->value);
free(list_entry(del,element_t,list));
}else {
s = list_entry(pos, element_t, list)->value;
number++;
pos = pos->prev;
}
}
return number;
```
### q_reverseK
這題我想用 reverse 的函數來寫，把程式碼分割之後一個一個丟進函數中再連接起來，函數的邏輯跟之前寫的 q_reverse 相同，但是因為丟入函數的佇列不會有 head ，所以一開始以為會有點麻煩，後來仔細想想，佇列的第一個元素根本不用做操作，所以從第二個元素開始走訪就好。
程式碼：
```c
void reverse(struct list_head *head,struct list_head *tail)
{
struct list_head *left = head;
tail = tail->next;
do {
struct list_head *tmp = head->next;
list_del(head->next);
list_add_tail(tmp,left);
left = left->prev;
}while (head->next != tail);
}
void q_reverseK(struct list_head *head, int k)
{
// https://leetcode.com/problems/reverse-nodes-in-k-group/
if (k==1 || !head || head->next == head)
return;
for (struct list_head *pos = head->next;pos != head;) {
struct list_head *tail = pos;
for (int i = 0;i < k-1;i++) {
tail = tail->next;
if (tail == head)
return;
}
reverse(pos,tail);
pos = pos->next;
}
}
```
依次把 head 的下一個節點丟到最左邊，直到 tail 。
遇到兩個困難，一開始我用 list_add_tail 但是要先刪除節點，所以我用 list_move 的概念實做：
```c
struct list_head *tmp = head->next;
list_del(head->next);
list_add_tail(tmp,left);
```
第二個問題，我沒有把 pos 指標處理好，我用 pos 指標和 tail 指標分別表示開頭跟結尾，假設要兩兩反轉1->2->3->4，我的指標會先在1跟2兩個位置，反轉完之後，我設置 :
`pos=tail->next`
希望 pos 指標能從2移動到3，但是由於我已經成功反轉了1跟2，所以指向1的 pos 指標還是指在1而 tail 也還是指向2，所以 tail 的 next 又會跑回1，應該設置 pos 的 next 就好，因為 pos 此刻必然在這一段排序好的佇列的最後一個位置。
### q_merge
把之前merge sort 當中的 merge 分離出來寫成獨立的 fuction merge two：
```c
struct list_head *head;
head = strcmp(list_entry(list1, element_t, list)->value,
list_entry(list2, element_t, list)->value) <= 0
? list1
: list2;
struct list_head *trace1 = list1;
struct list_head *trace2 = list2;
bool list1_bool = false, list2_bool = false;
do {
if (trace1 == head && list1_bool) {
struct list_head *tmp2 = trace2;
trace2 = trace2->next;
list_add_tail(tmp2, trace1);
list2_bool = true;
} else if (strcmp(list_entry(trace1, element_t, list)->value,
list_entry(trace2, element_t, list)->value) <= 0) {
trace1 = trace1->next;
list1_bool = true;
} else {
struct list_head *tmp2 = trace2;
trace2 = trace2->next;
list_add_tail(tmp2, trace1);
list2_bool = true;
}
} while (trace2 != list2 || !list2_bool);
return head;
```
有錯的程式碼：
```c
if (!head || head->next == head)
return 0;
else if (head->next->next == head)
return q_size(list_entry(head->next,queue_contex_t,chain)->q);
int num = q_size(head);
int firstPos = 0;
struct list_head *first = NULL;
struct list_head *tail;
for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
if (list_entry(pos,queue_contex_t,chain)->q->next != list_entry(pos,queue_contex_t,chain)->q) {
first = list_entry(pos,queue_contex_t,chain)->q->next;
list_del(list_entry(pos,queue_contex_t,chain)->q);
if (pos != head->next) //this 2
list_entry(pos,queue_contex_t,chain)->q = NULL;
break;
}else if (pos != head->next)
list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
firstPos++;
}
if (!first || firstPos == num)
return 0;
tail = first->next;
for (int i = firstPos+1;i < num; i++) {
if (list_entry(tail,queue_contex_t,chain)->q->next == list_entry(tail,queue_contex_t,chain)->q) {
list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
continue;
}
struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
list_del(list_entry(tail,queue_contex_t,chain)->q);
list_entry(tail,queue_contex_t,chain)->q = NULL;
first = merge_two(first,link);
tail = tail->next;
}
list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
if (descend)
q_reverse(head);
return q_size(list_entry(head->next,queue_contex_t,chain)->q);//this 5
```
走投無路，但突然發現有一個 size 欄位根本沒用到，所以我的很多判斷都可以簡化，然後應該也要更新 size 值：
```c
if (!head || head->next == head)
return 0;
else if (head->next->next == head)
return list_entry(head->next,queue_contex_t,chain)->size;
int num = q_size(head);
int firstPos = 0;
int totalSize = 0;
struct list_head *first = NULL;
struct list_head *tail;
for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
if (list_entry(pos,queue_contex_t,chain)->size != 0) {
first = list_entry(pos,queue_contex_t,chain)->q->next;
totalSize = list_entry(pos,queue_contex_t,chain)->size;
list_del(list_entry(pos,queue_contex_t,chain)->q);
if (pos != head->next) //this 2
list_entry(pos,queue_contex_t,chain)->q = NULL;
break;
}else if (pos != head->next)
list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
firstPos++;
}
if (!first || firstPos == num)
return 0;
tail = first->next;
for (int i = firstPos+1;i < num; i++) {
if (list_entry(tail,queue_contex_t,chain)->size == 0) {
list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
continue;
}
struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
list_del(list_entry(tail,queue_contex_t,chain)->q);
list_entry(tail,queue_contex_t,chain)->q = NULL;
totalSize += list_entry(tail,queue_contex_t,chain)->size;
list_entry(tail,queue_contex_t,chain)->size = 0;
first = merge_two(first,link);
tail = tail->next;
}
list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
if (descend)
q_reverse(head);
list_entry(head->next,queue_contex_t,chain)->size = totalSize;
return totalSize;//this 5
```
但還是錯。真的沒想法了，請 grok 幫我看一下問題：
```c
tail = first->next;//wrong
```
我明明是把 first 設置成第一個非空佇列的第一個非 head 元素，而 tail 則應該用來走訪每一個佇列，而不是佇列的節點，所以加入：
```c
tail = pos->next;
```
還有我想透過 q_reverse 生成遞減佇列，但是我不應該是把佇列的列表反轉，而是反轉佇列本身才對：
```c
q_reverse(list_entry(head->next,queue_contex_t,chain)->q);
```
改正後問題從：
```
# Test of insert_head, insert_tail, remove_head, reverse and merge
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
變成：
```
ERROR: Freed queue, but 2 blocks are still allocated
```
此時的程式碼：
```c
if (!head || head->next == head)
return 0;
else if (head->next->next == head)
return list_entry(head->next,queue_contex_t,chain)->size;
int num = q_size(head);
int firstPos = 0;
int totalSize = 0;
struct list_head *first = NULL;
struct list_head *tail;
for (struct list_head *pos = head->next; pos != head; pos = pos->next) {
if (list_entry(pos,queue_contex_t,chain)->size != 0) {
first = list_entry(pos,queue_contex_t,chain)->q->next;
totalSize = list_entry(pos,queue_contex_t,chain)->size;
list_del(list_entry(pos,queue_contex_t,chain)->q);
tail = pos->next;
if (pos != head->next) //this 2
list_entry(pos,queue_contex_t,chain)->q = NULL;
break;
}else if (pos != head->next)
list_entry(pos,queue_contex_t,chain)->q = NULL;//this 3
firstPos++;
}
if (!first || firstPos == num)
return 0;
for (int i = firstPos+1;i < num; i++) {
if (list_entry(tail,queue_contex_t,chain)->size == 0) {
list_entry(tail,queue_contex_t,chain)->q = NULL;//this 4
continue;
}
struct list_head *link = list_entry(tail,queue_contex_t,chain)->q->next;
list_del(list_entry(tail,queue_contex_t,chain)->q);
list_entry(tail,queue_contex_t,chain)->q = NULL;
totalSize += list_entry(tail,queue_contex_t,chain)->size;
list_entry(tail,queue_contex_t,chain)->size = 0;
first = merge_two(first,link);
tail = tail->next;
}
list_add_tail(list_entry(head->next,queue_contex_t,chain)->q,first);//this 1
if (descend)
q_reverse(head);
list_entry(head->next,queue_contex_t,chain)->size = totalSize;
return totalSize;//this 5
```
雖然測資沒有第一個佇列是空的，但這段程式碼是可以避免前面佇列是空的的問題。
然後我發現問題點了：題目要求將非第一個佇列皆設置為"空佇列"，並非"NULL" 所以我一直把指標直接設置成 NULL 完全是錯誤的，所以它才會一直跳出有記憶體空間沒有被刪除，我推測可能是外部函式尋找後面的空佇列進行釋放的時候，因為我設置成 NULL 所以節點沒辦法被找到進而無法刪除，我規格沒看清楚，卡了超級久。
接著，我把 merge sort 的 merge two 擷取出來變成一個 function ，然後交給 merge 使用，並且我改善了 merge sort的實做方式，不用切開 head:
```c
if (!head || head->next == head)
return 0;
else if (head->next->next == head)
return list_entry(head->next, queue_contex_t, chain)->size;
struct list_head *first = list_entry(head->next,queue_contex_t,chain)->q;
for (struct list_head *pos = head->next->next;pos != head;pos = pos->next) {
if(list_entry(pos,queue_contex_t,chain)->size != 0) {
merge_two(first,list_entry(pos,queue_contex_t,chain)->q);
list_entry(head->next,queue_contex_t,chain)->size += list_entry(pos,queue_contex_t,chain)->size;
list_entry(pos,queue_contex_t,chain)->size = 0;
}
}
return list_entry(head->next,queue_contex_t,chain)->size;
```
## 加入自訂指令
在 console.h 當中有定義巨集：
```c
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
```
會把我們加入的指令：
```c
ADD_COMMAND(shuffle,"shuffle queue","");
```
轉換為：
```c
add_cmd(shuffle,do_shuffle,"shuffle queue","")
```
再透過加入 do_shuffle 函數就可以新增一個指令。
### q_shuffle
```c
int len = q_size(head);
for (struct list_head *pos = head->prev ; len > 1 ;len--) {
int rand = rand()%(len - 1 + 1) + 1;
struct list_head *swap = head;
while (rand != 0) {
rand--;
swap = swap->next;
}
struct list_head *record = pos->prev;
list_del(pos);
list_add_tail(pos,swap);
list_del(swap);
list_add(swap,record);
pos = record;
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
