# 2019q1 Homework1 (lab0) contributed by < `bauuuu1021` > ## 作業目標 Your task is to modify the code in queue.h and queue.c to fully implement the following functions. - [ ] q new: > Create a new, empty queue. - [ ] q free: > Free all storage used by a queue. - [ ] q insert head: > Attempt to insert a new element at the head of the queue (LIFO discipline). - [ ] q insert tail: > Attempt to insert a new element at the tail of the queue (FIFO discipline). - [ ] q remove head: > Attempt to remove the element at the head of the queue. - [ ] q size: > Compute the number of elements in the queue. - [ ] q reverse: > Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) > Instead, it should rearrange the existing elements ## 實作紀錄 ### q size 在 sturct queue_t 中新增 `int size` 來紀錄 queue 中 element 數 且需留意 q = NULL 時 q->size 未被定義，故需額外處理 ### q insert head * 發現如果沒有先執行 `new` 來建立 queue，會出現以下的錯誤訊息 ```shell cmd>ih testtest Warning: Calling insert head on null queue q is NULL ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer Insertion of testtest failed q = NULL ``` 回到 q_insert_head() 中可以發現以下註解 ```C /* What should you do if the q is NULL? */ ``` 及 ```C /* Return false if q is NULL or could not allocate space. */ ``` 所以加上 ```C if (!q) return false; ``` 即解決 ### q insert tail * 為了在 O(1) 內完成操作，必須在 sturct queue_t 中加入指向 queue 尾端的 pointer * 實作與 q insert head 大致相同，需要注意的是第一個被插入 queue 的 element 可能不是呼叫 `ih` 而是呼叫 `it` 程式碼必須考慮這種情形下 q->head 之操作 ### q remove head * 題目要求 `copy the removed string to *sp`，原本使用 strdup()，但發現會造成以下問題 ```cmd cmd>rh asdf ERROR: Failed to store removed value ``` 後來以 strncpy() 取代 strdup()，即解決問題 * 在 `traces/trace-09-robust.cmd` 中的 `rhq` 會產生以下錯誤訊息 ```cmd ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer Removal failed ``` 使用 gdb 發現是 `q_remove_head()` 這個 function 出現問題 ```cmd Breakpoint 1, do_remove_head_quiet (argc=1, argv=0x555555761bc0) at qtest.c:341 341 rval = q_remove_head(q, NULL, 0); (gdb) s ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient Removal failed ``` 再重新閱讀 `rhq` 的作業需求 ： Remove from head of queue **without reporting value** 且 qtest.c 的 q_remove_head() 中原本用來承接 removed string 的參數為 NULL ```C=341 rval = q_remove_head(q, NULL, 0); ^ ``` 所以將原本的函式多加上檢查 sp 的判斷條件，修改如下 ```C if (sp) { memset(sp, 0, bufsize); strncpy(sp, tmp->value, bufsize - 1); } ``` :::info TOTAL 100/100 ::: ## strcpy 與 strdup 比較 ## 參考資料 * [github link](https://github.com/bauuuu1021/lab0-c) * [作業要求](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) ###### tags: `bauuuu1021`, `sysprog`,`2019spring`