# linked list 使用習慣養成
請試著就給定的資料與實測結果，嘗試解說自動測試程式如何因應不同的程式碼，提示開發者錯誤，幫助開發者實現幾個目標。一、認識 list.h 函式的使用方法與限制。二、養成正確的探測能力，在有限的測試裡，整理程式在各階段與輸出的距離。三、理解自動程式的運作原理與巧思。
### delete_dup
以下程式為 delete duplicate 簡稱 dedup ，已知160行函式須搭配159行函式，否則會有 segmentation fault。147行 if 句型須先於150,158行 if 句型，否則也會有 segmentation fault。若需引用成功的程式碼，請試著比較分支的處理，即 if 條件式的位置與 list_for_each_entry_safe 迴圈的語法，其產生的效果探討程式撰寫風格，幫助在下完成開發此段落程式。
```cpp!
/* Delete all nodes that have duplicate string */
137 bool q_delete_dup(struct list_head *head)
138 {
139 // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
140 if (!head)
141 return false;
142 element_t *cur, *new;
143 int N_del = 0;
144 bool flag = false; /*indicating end of duplicate string */
145 list_for_each_entry_safe (cur, new, head, list) {
146 /* break condition */
147 if (&new->list == head)
148 continue;
149 /* string conparison */
150 if (!strcmp(cur->value, new->value)) {
151 if (flag == false) {
152 N_del = 2;
153 flag = true;
154 } else
155 N_del++;
156 }
157 /* delete */
158 if (N_del > 0 && flag == true) {
159 list_del(&cur->list);
160 q_release_element(cur);
161 N_del--;
162 if (N_del == 0)
163 flag = false;
164 }
165 }
166 return true;
167 }
```
測試結果：
可嘗試8次錯誤，只能處理開頭的重複字串，不能處理多組重複字串，或是表單中後的重複字串。
```shell!
urbaner:~/Documents/linux2023/lab0-c$ ./qtest
cmd> new
l = []
cmd> ih app 3
l = [app app app]
cmd> it be
l = [app app app be]
cmd> it car 2
l = [app app app be car car]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [be ... ]
ERROR: Queue has more than 1 elements
cmd> list
Unknown command 'list'
cmd> show
Current queue ID: 0
l = [be ... ]
ERROR: Queue has more than 1 elements
cmd> free
l = NULL
cmd> ih app 3
Warning: Calling insert head on null queue
l = NULL
cmd> new
l = []
cmd> ih app 3
l = [app app app]
cmd> it be
l = [app app app be]
cmd> it car
l = [app app app be car]
cmd> dedup
l = [be car]
cmd> it car
l = [be car car]
cmd> dedup
ERROR: Duplicate strings are in queue or distinct strings are not in queue
l = [be ... ]
ERROR: Queue has more than 1 elements
cmd> ih be 2
l = [be be be ... ]
ERROR: Queue has more than 3 elements
cmd> dedup
l = [ ... ]
ERROR: Queue has more than 0 elements
cmd> show
Current queue ID: 0
l = [ ... ]
ERROR: Queue has more than 0 elements
Error limit exceeded. Stopping command execution
cmd> it tet
cmd> show
cmd> ih ale
cmd> show
```
還不清楚 entry, node 在 for 迴圈的角色。錯誤草稿，很懷疑一次迴圈能不能成功搜尋所有錯誤。
```cpp!
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
element_t *val1, *val2, *cur, *safe;
struct list_head *pre = head->next;
int mulp = 1;
val2 = list_entry(pre, element_t, list);
list_for_each_entry(cur,pre,list){
val1 = list_entry(&cur->list, element_t, list);
if(strcmp(val1->value, val2->value) == 0){
list_del(val1);
q_release_element(cur);
break;
}
else
printf("mulp is %c\n",mulp);
}
//delete cur dup
return true;
}
```
修改為一層迴圈，在重複節點相鄰情形。若不相鄰，改用兩層迴圈。
```cpp!
else{
nnew = list_entry(&cur->list, struct list_head, list);
cur = list_entry(nnew->next, element_t, list);
continue;
}
}
... /* comparison */
else {
nnew = &cur->list;
cur = list_entry(nnew->next, element_t, list);
continue;
}
}
```
還未熟悉指標和 entry 函式的差別的慘況，留著當警惕。
最後程式提醒我，沒有回傳值，參考幾位同學，[true tail1](https://hackmd.io/@willwillhi/lab0-2023), [true tail2](https://hackmd.io/@alanjian85/lab0-2023#q_delete_dup), [判斷頭](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup), 發現我也不大明白這個函式為什麼要使用 bool 宣告，明明大家都沒有作什麼判斷，回傳也沒有什麼用處。所以我也學習yanjiew 判斷表單頭是否為空，在結尾回傳 true ，是為 true tail。
```sh!
l = [app app app bear car];
dedup;
...
(gdb) p *new
$13 = {value = 0xdeadbeef <error: Cannot access memory at address 0xdeadbeef>, list = {
prev = 0x5555555682a8, next = 0x5555555681f8}}
(gdb) p head
$14 = (struct list_head *) 0x555555567fa0
(gdb) p &new->list
$15 = (struct list_head *) 0x555555567fa0
```
測試到這裡發現，[q_delete_dup](https://hackmd.io/@willwillhi/lab0-2023#%E5%AE%8C%E6%88%90-queuec)，if 條件式不夠完善，在 cur= `&node("car")` 時，new = head ，此時 new->value 無法存取，因為 head 沒有 value，所以適當修正 if 判斷的條件式，為 `!strcmp(cur->value, new->value) || &new->list != head` ，對第一個 if 用來判斷是否為重複字串。
最後注意迴圈的控制，即可完成。 trace 06 尚未通過，截取 dedup 命令部份作測試。可以選擇忽略 RAND 部份的節點。
479 qtest.c 迴圈 ; 503 free function in qtest.c ; 508 q_show
console.c free 203 loop 690up
暫時看不懂這一帶的程式，只知道 qtest 裡 do_dedup 有預設一個情景，我剛好卡在這裡遇上了，出不去。
沒想到，自己因為邏輯昏亂沒有注意，必須使用 list_for_each_entry_safe 理由是走訪 entry ，需要 safe 。特別需要用到 entry 內存取的值排序。
```cpp!
bool q_delete_dup(struct list_head *head)
{
// https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
element_t *cur, *safe;
struct list_head *pre = head->next;
list_for_each_entry_safe(cur,safe,pre,list){
if(!strcmp(cur->value, safe->value) && &safe->list != head){
list_del(&cur->list);
q_release_element(cur);
break;
}
else {
//nnew = &cur->list;
cur = list_entry(cur->list.next, element_t, list);
continue;
}
}
//delete cur dup
return true;
}
```
:::warning
建議可以看看 `queue.h` 檔案，裡面有規範每一個函式的行為。`queue.h` 裡面有寫，當 `list` 是 NULL 或空的時候，要回傳 false。
> [name=yanjiew1]
:::
### sort
splice 可以合併表單，或是新增頭，需要一個無值的頭，在前或在後。
### static check
```cpp=
/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
/* Try to use merge sort*/
if (!head || list_empty(head) || list_is_singular(head))
return;
/* Find middle point */
struct list_head *mid, *left, *right;
left = right = head;
do {
left = left->next;
right = right->prev;
} while (left != right && left->next != right);
mid = left;
/* Divide into two part */
LIST_HEAD(second);
list_cut_position(&second, mid, head->prev);
/* Conquer */
q_sort(head, descend);
q_sort(&second, descend);
q_view(head), puts(""), q_view(&second);
/* Merge */
merge_two(head, &second, descend);
q_view(head);
}
/*merge two sorted lists, as one sorted list*/
static void merge_two(struct list_head *l1, struct list_head *l2, bool descend)
{
if (!l1 || !l2)
return;
>>>>>>247>>>>>> element_t *nod1, *nod2, *ext; /* extreme value */
bool state;
LIST_HEAD(newhd);
while (!list_empty(l1) && !list_empty(l2)) {
nod1 = list_first_entry(l1, element_t, list);
nod2 = list_first_entry(l2, element_t, list);
if (!descend)
state = strcmp(nod1->value, nod2->value) < 0;
else
state = strcmp(nod1->value, nod2->value) > 0;
ext = state ? nod1 : nod2;
/* add node to tail of newhd list */
list_move_tail(&ext->list, &newhd);
}
if (list_empty(l2))
list_splice_tail_init(l1, &newhd);
else
list_splice_tail_init(l2, &newhd);
list_splice(&newhd, l1);
}
/* Function of view list content */
void q_view(struct list_head *head)
{
element_t *now;
list_for_each_entry (now, head, list) {
>>>>143>>>>> printf("%s ", now->value);
if (now->list.next == head)
printf("&&&!\n");
}
}
```
```shell!
Following files need to be cleaned up:
queue.c
queue.c:247:16: style: The scope of the variable 'nod1' can be reduced. [variableScope]
element_t *nod1, *nod2, *ext; /* extreme value */
^
queue.c:247:23: style: The scope of the variable 'nod2' can be reduced. [variableScope]
element_t *nod1, *nod2, *ext; /* extreme value */
^
queue.c:143:28: error: Uninitialized variable: now->value [uninitvar]
printf("%s ", now->value);
^
Fail to pass static analysis.
```
```cpp
+ while (!list_empty(l1) && !list_empty(l2)) {
+ element_t *nod1, *nod2, *ext; /* extreme value */
+ nod1 = list_first_entry(l1, element_t, list);
1 element_t *now;
142 now = head->next;/* Cppcheck init error */
1 list_for_each_entry (now, head, list) {
```
### swap
```cpp!
void q_swap(struct list_head *head)
{
/* https://leetcode.com/problems/swap-nodes-in-pairs/ */
char *tmp;
element_t *first, *second;
struct list_head *cur, *new;
int count = 1;
list_for_each_entry_safe (cur, new, head, list) {
struct list_head *node = &new->list;
if (cur && new &&node != head && count % 2 == 1) {
tmp = cur->value;
cur->value = new->value;
new->value = tmp;
}
count++;
}
}
```
### reverse
```cpp!
void q_reverse(struct list_head *head)
{
struct list_head *node, *back;
element_t *now, *far;
char *tmp;
back = head->prev;
list_for_each (node, head) {
if (node == back)
break;
now = list_entry(node, element_t, list);
far = list_entry(back, element_t, list);
tmp = now->value;
now->value = far->value;
far->value = tmp;
if (node->next == back)
break;
back = back->prev;
}
}
```
### merge
print queues
```cpp!
if (!head || list_empty(head))
return 0;
queue_contex_t *nd_qc;
//fir_qc = list_first_entry(head, queue_contex_t, chain);
list_for_each_entry(nd_qc, head, chain){
q_view(nd_qc->q);
}
return 0;
```
source:
https://hackmd.io/-Jik_Z6fTqCo3w_3odMc2w?both
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Pointers:" -> "Values:" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
pointers [label="<f0> cur1/first1 | <f2> last1 | <f1> cur2/first2 | <f3> last2", color=white];
values [label="<f0> 1 | <f1> 2 | <f2> 7 | <f3> 8 | <f4> 3 | <f5> 4 | <f6> 5 | <f7> 6"];
{ rank=same; "Pointers:"; pointers }
{ rank=same; "Values:"; values }
edge [color=blue];
pointers:f0 -> values:f0;
pointers:f1 -> values:f4;
pointers:f2 -> values:f3;
pointers:f3 -> values:f7;
}
```
# Github
## home and office
with gitk and tig, I can see how git and github work together. Standard now is to commit before every git push and pull, and merge would go with pull. Commit check the status. Also git log is important.
Maybe git map graph would help. Make sure you can see two places use the same code in hackmd and github. Every time doing synchorizing, `git pull`, `git add`, `git merge`
vim queue.c; `git add`, `git commit -a`
Merge, Home. after updating; dedup accepted; 03242205
and then the pull with merge is executed, on tig and gitk is the same exactly.
"Your branch is ahead of 'origin/master' by 2 commits." 03242205 2 commits which is pull and merge.
All in all, commit is to think, between remote(github) and local(git)
[fix,0324](https://github.com/Urbaner3/lab0-c/commit/777d60dd6611b55b3a7c4fc9a3274a7ffa96f0f9?diff=unified#diff-3f6f16518a74b523b2cad7ede4d4a9c11605317dfed2905cdaf12e242ee05923L120) says that in dedup, two branch is not matched.
Consider use branch to load the local tig message, so the thing would be clear. `void q_sort(struct list_head *head)` is deleted twice.
`git checkout --ours cute_animal.jpg`[detail](https://gitbook.tw/chapters/branch/fix-conflict)
branch 自己整理，和統一進度，看起來不存在，但在實作時，會出現問題，所以要想標準動作，讓 git 可以順利運作，這樣子我就真正的能夠與別人合作。想想存檔和讀取的方式，好好想想遊戲的運作。
There is red dot in gitk and Unknown in tig, so the tree remember!!
:house: >>>>>>>
```shell!
git log
commit b65f692d80f5dabeb08e796044e87e370231dcbf (HEAD -> master)
Author: Peter Chen <urbaner3@gmail.com>
Date: Fri Mar 24 22:37:55 2023 +0800
React to conflict, home, del_mid checked and to fix
commit c76bcb06d633cd5f1f18f42dc73fbe5d1ab6bb0d
Merge: a3a2f79 777d60d
Author: Peter Chen <urbaner3@gmail.com>
Date: Fri Mar 24 21:57:33 2023 +0800
Merge, Home; after updating; dedup accepted
commit a3a2f7986c57c7053556f91eabb720a082fb80cd
Author: Peter Chen <urbaner3@gmail.com>
Date: Fri Mar 24 21:10:57 2023 +0800
Update by merge,between office and home
commit 777d60dd6611b55b3a7c4fc9a3274a7ffa96f0f9 (origin/master, origin/HEAD)
Merge: 4ede666 350bd15
Author: Urbaner3 <urbaner3@gmail.com>
Date: Fri Mar 24 16:49:05 2023 +0800
```
`git push`
commit 好像是起手勢，但只有成功的會存在，或說是merge 前的會存在。
Next is to take in commands, reset, rebase, revert. HEAD, origin two branches. Also reflog memo is useful `git log --oneline`,`git rebase -i bb0c9c2` `git checkout cat`. Following the chop-preem process is tiring. `git diff queue.c` is helpful to see where I am. `777d60d..b65f692 master -> origin/master` I can't see the sum code on my local branch, office.
Pull=fetch is also need run, not familar is a shame. [Page](https://gitbook.tw/chapters/github/pull-from-github)
two branches merge need specify, `git config pull.rebase false`
Sometimes it specifies undergoing commit, one can miss that. `git log` shows colorful branch label. `git merge master`
0325 without branch, because remote is done on home, I can't stay syncced and then push. But file is syncced. Just go on. 2010 evenning, finish merge sort. `git commit -a`,`git push`
```shell
38eb1a4 (HEAD -> office) Implement of merge_two and sort
d19c725 (master) Merge branch master, Urbaner3 to master_office
b4bc4d4 Pull commits,descend,Office get
b65f692 (origin/master, origin/HEAD) React to conflict, home, del_mid checked and to fix
c76bcb0 Merge, Home; after updating; dedup accepted
a3a2f79 Update by merge,between office and home
777d60d Fix the confict, del_mid need adapt
```
### Git and Github @James
遊戲存檔，不同資料夾不同電腦。
[系列](https://www.youtube.com/watch?v=Zd5jSDRjWfA&list=PLz-S_Wd1N3svV8XnuDM6CPaTCtQkk5SY4)
`git reset -- filename`,unstage. `git checkout -- filesname`,discard changes, `git reset --soft HEAD~n`
預設：開啟共作目錄, `git init`, `git remote add origin (link)`, `git push -u origin main`, 新建資料夾，`git clone ...`
`git checkout -b branch-name`
B: 1.txt=222222 , commit=Add new file
A:1.txt = 777. commit=Change 1
git push, B: 3.txt=333 commit=新功能完成 , branch: new-feature
`git push`, fail. `git push -u origin new-feature(HEAD)`
PR:pull request, merge and push
browser: branch , PR fail, to do FF or rebase.
`git switch branch` `git rebase master` conflict, `git rebase --continue` `git push` fail: git log local and remote is not inclusive. !!! `git push -f` 用在分支上面
回去作 PR merge 完可刪除
M&B:`git pull`on A,B. A:1.txt=666 commit=change 1 on A
B:1.txt=345 2.txt=+345 commit=change 1&2 commit on 3.txt on branch:new-feature2. switch to master and `git merge new-feature2` 無注意 A 更新沒 pull; push with conflict! `git pull` conflict `git commit -a` `git push`
0326 After merge, do push again, so that github would receive the result. And then you may leave.
# 參考資料
[qwe助教2021](https://hackmd.io/@qwe661234/qwe6612342021q1HW1#%E6%B8%AC%E8%A9%A6%E7%B5%90%E6%9E%9C)
# 測試程式 與 控制台導覽
console_init() in qtest.c:1015 like console.c, adding command items.
1065 Signal handlers
1185 main
bool exception_setup in harness.c:253
report_event in report.c:54
命令直譯器的初始化準備 -> `void init_cmd` in console.c:422
void add_cmd in console.c:76
檢測非預期的記憶體操作或程式執行逾時 > do_fun in qtest.c
example:
```shell!
l = NULL
cmd> new
l = []
cmd> ih My
l = [My]
cmd> it name
l = [My name]
cmd> it is
l = [My name is]
cmd> it Peter.
l = [My name is Peter.]
cmd> new
l = []
cmd> show
Current queue ID: 1
l = []
cmd> it Apple
l = [Apple]
cmd> it Bear
l = [Apple Bear]
cmd> it Cow
l = [Apple Bear Cow]
cmd> it deer
l = [Apple Bear Cow deer]
cmd> ih Strings
l = [Strings Apple Bear Cow deer]
cmd>
```
# web server
linenoise linenoise.c:1184 trace1212-> line_raw() linenoise.c:1123 trace1132 -> line_edit() linenoise.c:896 trace930 while(1)
Sign in with Wallet
Connect another wallet