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，會出現以下的錯誤訊息

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() 中可以發現以下註解

/* What should you do if the q is NULL? */

及

/* Return false if q is NULL or could not allocate space. */

所以加上

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>rh asdf
ERROR: Failed to store removed value

後來以 strncpy() 取代 strdup()，即解決問題

• 在 traces/trace-09-robust.cmd 中的 rhq 會產生以下錯誤訊息

ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
Removal failed

使用 gdb 發現是 q_remove_head() 這個 function 出現問題

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

​​​rval = q_remove_head(q, NULL, 0);
​​​                         ^

所以將原本的函式多加上檢查 sp 的判斷條件，修改如下

​​​if (sp) {
​​​     memset(sp, 0, bufsize);
​​​     strncpy(sp, tmp->value, bufsize - 1);
​​​ }

TOTAL 100/100

strcpy 與 strdup 比較

參考資料

• github link
• 作業要求

tags: bauuuu1021, sysprog,2019spring