# 2025q1 第 1 週測驗題

## quiz 1
雙倍指標，打包再打包的概念，包起 dereference 的內容。不管哪種都會讓串列變成樹。一個追趕的演算法，只是追和被追有沒有用 next 連在一起而已。下方有示意圖。[^dot_rf1]; [^dot_rf2]。或說，讓 *p 指標用來存取所有的 next，另外，prev 也可以用類似的操作。雙指標不是物件的指標，是走遍指標的指標變數。

l->1  2   3   4   5   6  7  8
           be->
          *p->
          *p->it
l->1  2   3   4   5   6  7  8
	  .->it
	  it->4
l->1  2   3   it  4   5  6  7  8

digraph linked_list {
    rankdir=LR;  // 水平顯示
    node [shape=record, style=rounded];

    head [shape=circle, label="head", style=filled, fillcolor=lightblue];
    A [label="A"];
    B [label="B"];
    C [label="C"];
    null [shape=plaintext, label="NULL"];

    head -> A;
    A -> B;
    B -> C;
    C -> null;
}

AAAA = &l->head
BBBB = before
CCCC = &(*p)->next
DDDD = item->next
都和教材 append 的程式碼相對應，只有 DDDD 是新增的。

### 解釋上方程式碼運作原理
善用 `gcc -E quiz1a.c > quiz1a.i`, `gcc -g -o quiz1a quiz1a.c` 處理錯誤。因為有兩個巨集，影響預編譯的結果。而且是**合成**影響。
main -> test_suite -> [my_run_test(test_list);] = do-while(0) -> [test()] = test_list()
說真的，一步到位我還是有點暈，但預處理器成功了。test_list 函式有三步驟。

#### 測試開頭插入

像堆疊一樣，倒數插入 items[i] ，從 i=0 到 999，但都插入在開頭，所以從開頭會是 999 數回 0。在 list_insert_before 函式執行之前， list_reset 只是建立節點，沒有串聯成串列，所有節點都是孤單的節點。注意 `do-while(0)` 是假迴圈，因為不會重複執行，只剩下名字。理頭都是預留給可能的錯誤，去判斷並回傳錯誤。如果 test_list 結束，測試成功回傳 NULL。

#### 其他兩段測試

其實仔細看，只有一個測試，最後一段是類似測試但實作。一次說明，這次插入尾端，從 0 到 9999 。檢察長度，和各節點數值。就結束了。輸出 測試成功， run 次數 1，一次成功，一杆進洞。那個巨集是模仿 assert 和 printf 實作的。最後的 `return !!result;` 注意是字串對布林變數的 1, 0 真假反轉。用 felo search 有詳細說明，容易邏輯死亡，小心服用。摘錄一段：
>In C, the expression return !!NULL; involves the use of the logical NOT operator (!) applied twice to the NULL macro.

### 在現有的程式碼基礎上，撰寫合併排序操作

嘗試運用 macro 測試在 static list_t *list_setup 函式中，但 macro 會被預處理的 return 影響，就算另外新增變數儲存也沒辦法。這是設計的問題。我發現我函式呼叫，即使不傳回串列頭的指標，初始構建和測試仍然可行。於是修改回傳型別配合 macro ，也算是發現 macro 的一大缺點。

#### test point chosen
context:

#0  list_size (mylist=0x55555555bee0 <l>) at quiz1a.c:90
#1  0x000055555555532b in test_list () at quiz1a.c:55
#2  0x0000555555555422 in test_suite () at quiz1a.c:78
#3  0x00005555555554f5 in main () at quiz1a.c:107

當有錯務時，回報機制在位址的錯誤，沒有辦法存取到。應該說是分頁錯誤的問題， gdb 可以讀取錯誤訊息，但是被 printf 的錯誤訊息中斷了。也就是兩個都要回傳，但不能同時回傳。

517	./stdio-common/vfprintf-internal.c: No such file or directory.
(gdb) frame 3
#3  0x000055555555569e in main () at merge.c:137
137	    printf("ERROR: %s\n", result);
(gdb) p result
$7 = 0x5 <error: Cannot access memory at address 0x5>
(gdb) type result
Undefined command: "type".  Try "help".
(gdb) ptype result
type = char *
(gdb) p *result
Cannot access memory at address 0x5

# second test

(gdb) where
#0  list_size (mylist=0x55555555bfb8 <lsa>) at merge.c:90
#1  0x000055555555526a in list_setup (l=0x55555555bfb8 <lsa>, 
    l_items=0x55555555bf00 <a_items>, length=5, array=0x7fffffffd7e0)
    at merge.c:24
#2  0x0000555555555678 in main () at merge.c:135
(gdb) l
85	  list_item_t *curr;
86	  curr = mylist->head;
87	  int count = 0;
88	  while (curr) {
89	    count++;
90	    curr = curr->next;
91	  }
92	  return count;
93	}
94	
(gdb) p count
$1 = 1
(gdb) p curr
$2 = (list_item_t *) 0x55555555bf00 <a_items>
(gdb) p curr->next
$3 = (struct list_item *) 0x55555555bf10 <a_items+16>
(gdb) p curr->next->next
$4 = (struct list_item *) 0x55555555bf20 <a_items+32>
(gdb) p *curr->next->next
$5 = {value = 5, next = 0x55555555bf30 <a_items+48>}

修改程式碼，前置處理器部分：

#define setup_run_test(test, l, l_items, length, array) \
    do {                                               \
        char *message = test(l, l_items, length, array); \
        tests_run++;                                   \
        if (message)                                   \
            return message;                            \
    } while (0)

並對 list_setup 加上 `return NULL`，完成回傳值，如果通過測試的話。原來直接輸入參數就可以但一定要注意資料的層數，結構都必須是全域的。

_GI__IO_puts (str=0x5555555560ac "ALL TESTS of List PASSED") at ./libio/ioputs.c:33
33	./libio/ioputs.c: No such file or directory.
(gdb) 
35	in ./libio/ioputs.c
(gdb) 
__strlen_avx2 () at ../sysdeps/x86_64/multiarch/strlen-avx2.S:50
50	../sysdeps/x86_64/multiarch/strlen-avx2.S: No such file or directory.

如果 printf 正常的話，用 `cont`, `step`, `until N`, 跳過迴圈和一些步驟。完成偵錯程序。

## quiz 2

## quiz 3