2018q3 Homework2 (lab0)
contributed by < DyslexiaS
>
作業說明
C Programming Lab
git commit message 應該以動詞開頭,具體寫出做了什麼修改。如 "New Q" 這段訊息應改為 "Implement …"
課程助教
實驗環境
更換遠端伺服器倉庫網址
將 git repository 的 https 改為 ssh,並且設定好 ssh-key,之後 git push 就不需要輸入帳號密碼
過程
queue_t data struct
由於 q_size 和 q_insert_tail 都要求 的時間複雜度,因此需要隨時去紀錄 tail 和 size
q_insert_head
q_insert_tail
q_free
- 先把 element 清除乾淨才能 free 掉 queue
q_remove_head
strncpy description
Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
- 在第 8 行的地方卡了很久,因為在做 strncpy 並沒有複製到 terminating null byte ('\0'),造成字串後面多了很多奇怪的東西,加上 '\0' 就解決了
strdup description
The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
- 在第 11 行的地方,tmp->value 是由 strdup 在 free 掉 element 之前需要先 free 掉裡面的 value,但執行第 10 行卻會造成錯誤,後來發現有其他同學也遇到相同的狀況。
- harness.h 有段 macro 會把 free 替換成自己的函式,因此我們所用的 free 不是真的 free
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
q_reverse
- 一開始想要用兩個 tmp 去紀錄當前的 node 以及 下一個 node,後來同學提醒可以用 tail->next 去紀錄,便能省去在創一個暫存的空間了
- 一開始還把 node 數為 1, 2 的狀況獨立出來寫,但後來發現可以全部都使用同一個 while 來解決~
步驟
藍色箭頭為 node 指向位置
黑色箭頭才是 node->next
紅色箭頭為當次轉向的動作
-
將 tail 指向 head,所以現在 tail 和 head 都是第 1 個 node
-
將 tmp 賦值成 head->next (也就是第 2 個 node)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
開始做 while 迴圈,結束條件為 tmp == NULL,因此當節點只有 1 個時,便不會做以下步驟
-
將 tmp->next 存起來,才不會讓 a2 指向 a1 後,取不到 a3
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
將 tmp(a2) 轉向,指到 a1
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
-
將 HEAD 和 tmp 往前推進
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- 重複以上 step4 - step6
- 跳出迴圈時,tmp 是 NULL, tail->next 也剛好是 NULL,因此也省掉手動把 tail->next 變成 NULL (一舉兩得
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- 結束時
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
qtest 的行為和技巧
void *test_malloc(size_t size) <harness.h>
在 harness.h 裡有這麼一段 macro:
因此我們使用 malloc 時,其實是用了 test_malloc,接著來看看 malloc 實際上會做什麼事情,以下以 doubly-linked list 來對 blocks 進行操作
節錄 test_malloc:
當我們 malloc 一個 list_ele_t
時,會被夾在 magic_header 和 find_footer 回傳的 footer 中間

其中unsigned char payload[0];
是一不佔空間的變數(Struct Hack技巧),用來存 list_ele_t
的起始位置
GCC manual 6.17 : Arrays of Length Zero (Flexible array member)
- 實際 malloc 的大小會是三塊加起來,MAGICHEADER, MAGICFOOTER 就是用來標記
list_ele_t
邊界的紀錄點,因此在 test_free() 裡,footer != MAGICFOOTER
就會有 MSG_ERROR
Corruption detected in block with address %p when attempting to free it
C99 Flexible array member:
以上 code 會有潛在的 stack smashing detected 問題
詳見
自動評分系統運作原理
GitHub