# 2018q3 Homework2 (lab0)
contributed by < [Jyun-Neng](https://github.com/Jyun-Neng) >
>請補上實驗環境
>[name=課程助教][color=red]
* 修改 `Makefile`
* 刪除以下兩行則執行 `make` 指令後便不會產生 `handin.tar`
```shell
-tar -cf handin.tar queue.c queue.h
tar cf handin.tar queue.c queue.h
```
:::info
`handin.tar` 的存在是為了 CMU Autolab 使用，以我們的使用情境來說，的確多餘，歡迎送 pull request 過來
:notes: jserv
:::
# Implementation of Queue
## Queue Structure
* 新增記錄 queue 內 element 總數的 `size`
* 新增 pointer to tail node in queue。
```clike=
typedef struct {
list_ele_t *head; // pointer to head element
list_ele_t *tail; // pointer to tail element
int size; // queue size
}
```
## Create empty queue
* 需要判斷若 malloc 回傳 NULL 的情況。
```clike=
if (q) {
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
```
## Free all storage used by queue
* 釋放 queue 的空間
* 釋放 queue 內 element 的空間
::: warning
雖說若 q 是 NULL 則 `free(q)` 不會運作，
但 `pos = q->head` 在 q 是 NULL 的情況下會導致 segmantation fault。因此，仍需要判斷 q 是否為 NULL。
:::
```clike=
if (!q) // prevent to execute line 4
return;
list_ele_t *pos = q->head;
while (pos) {
list_ele_t *tmp = pos;
pos = pos->next_node;
free(tmp);
}
free(q);
```
## Insert element at head of queue
* 判斷 queue 是否為 NULL。
* 判斷 malloc 新的 element 是否回傳 NULL。
* queue size 要增加。
* 要考慮 tail pointer，當加入第一個 element 時 tail pointer 也須指向此 element。
```clike=
if (!q)
return false;
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh) {
newh->value = strdup(s);
newh->next = q->head;
q->head = newh;
if (++(q->size) == 1)
q->tail = q->head; // tail node should be asigned at first insertion
return true;
}
return false;
```
## Insert element at tail of queue
* 判斷 queue 是否為 NULL。
* 判斷 malloc 新的 element 是否回傳 NULL。
* queue size 要增加。
* 要考慮 head pointer，當加入第一個 element 時 head pointer 也須指向此 element。
```clike=
if (!q)
return false;
list_ele_t *newt;
newt = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newt) {
newt->next = NULL;
newt->value = strdup(s);
if (++(q->size) == 1)
q->head = newt; // head node should be assigned at first insertion
else
q->tail->next = newt;
q->tail = newt;
return true;
}
return false;
```
## Remove element from head of queue
* 當 q 或者 q->head 是 NULL 時，回傳 false。
* queue size 要減少。
* 要釋放移除的 element 的記憶體空間。
* 要顯示移除的 element 內記錄的字串。
* 複製移除字串。
:::danger
若 `sp` 不是 NULL，被移除的 element 內儲存的字串需複製到 `sp` 且要比較字串長度及`bufsize`，若字串長度大於 `bufsize-1` ，僅複製 `bufsize-1` 的字串。反之，則複製整個字串大小，且最後都需加入 null character。
:::
```clike=
if (!q || !(q->head))
return false;
list_ele_t *tmp = q->head;
unsigned long size;
if (sp) { // copy the removed string
size = strlen(tmp->value);
size = (size > bufsize - 1) ? bufsize - 1 : size;
strncpy(sp, tmp->value, size);
sp[size] = '\0';
}
q->size--;
q->head = q->head->next;
free(tmp);
return true;
```
> free 字串會出現 double free error 是 strdup 惹的禍，因為 harness.h 有段 macro 會把 free 換成一個自己開發的函式，導致你用不到真正的 free ，變成在用 malloc 與 test_free ，因此直接用 malloc 讓 preprocessor 把它也轉成 test_malloc 就好了。
> [name=pjchiou] [time=2018 Sep 27 Thu 05:58]
## Return number of elements in queue
* 由於我們已經在 queue structure 新增記錄 size 的變數，因此只需回傳當前紀錄queue大小的 size 變數即可，運算時間及為 $O(1)$。
* 若queue已經被釋放記憶體空間或根本沒有queue存在，直接回傳 0。
```clike=
return (q) ? q->size : 0;
```
## Reverse elements in queue
* 當不存在 queue、queue 內是空的、只有一個 element，不需動作。
* 需要三個 pointers 來記錄當前、下一個、前一個的 element。
* Time complexity: $O(n)$
```clike=
next = q->head->next;
prev = q->head;
while (next) {
pos = next;
next = next->next;
pos->next = prev;
prev = pos;
}
```
# Test Results
```shell
$make test
.
.
.
TOTAL 100/100
```
:::info
分析測試的結果，剩餘的錯誤是因為尚未完成 reverse 所導致，其餘的部分皆已完成且通過測試。
:::
> 未完成 reverse 的測試結果: 81/100
> [name=Lawrence][time=Sat, Sep 22, 2018 11:35 PM]
:::danger
Reverse 完成後發現 remove 是有問題的，string copy 沒有分辨好要複製的長度及沒有加 null character。
> [name=Lawrence][time=Sun, Sep 23, 2018 3:34 PM]
:::
> 修改完 copy string 的問題後測試完成: 100/100
> [name=Lawrence][time=Sun, Sep 23, 2018 3:36 PM]
>
:::danger
請繼續更新！
-- 課程助教
:::
# 自動評分系統
## `driver.py`
### `getopt`
`optlist, args = getopt.getopt(args, 'hp:t:v:A')`
這段程式碼將所需的參數存到 `optlist`
[Python documentation -- getopt](https://docs.python.org/2/library/getopt.html)
* Parses command line options and parameter list. args is the argument list to be parsed, without the leading reference to the running program. Typically, this means `sys.argv[1:]`. options is the string of option letters that the script wants to recognize, with options that require an argument followed by a colon (`:` ; i.e., the same format that Unix getopt() uses).
```python
>> import getopt
>> args = ['-h', '-p', 'xx', '-t', 'xxx', '-v', 'xxxx', '-A']
>> optlist, args = getopt.getopt(args, 'hp:t:v:A')
>> optlist
[('-h', ''), ('-p', 'xx'), ('-t', 'xxx'), ('-v', 'xxxx'), ('-A'. '')]
>> args
[]
```
### `runTrace`
`runTrace` 為執行測試指令的函式
```python
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.qtest, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
print "Call of '%s' failed: %s" % (" ".join(clist), e)
return False
```
`retcode = subprocess.call(clist)`
等同於執行 command line `./qtest -v -f ./traces/file.cmd`，`qtest` 便會執行 `file.cmd` 的指令來測試。
## `qtest.c`
測試程式的指令是由 `console.[ch]` 來管理，且是用 linked list 來儲存新增的指令。
```C
/* Information about each command */
/* Organized as linked list in alphabetical order */
typedef struct CELE cmd_ele, *cmd_ptr;
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
Sign in with Wallet
Connect another wallet