# 2018q3 Homework2 (lab0)
contributed by < [`jason53415`](https://github.com/jason53415/lab0-c) >
>commit 應切分為更小的 commit，每個 commit 都應該專注在小部份的修改
>[name=課程助教][color=red]
## 測試環境
```
$ uname -a
Linux scream-47860 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
```
## 實做內容
### queue.h
* 為了要達成可以 $O(1)$ 時間取得 queue 的大小以及從尾端插入元素，需要在 queue.h 中的 `queue_t` 增加 `list_ele_t *tail` 指向 queue 的末端，以及 `int size` 記錄 queue 的大小。
```C=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
int size;
} queue_t;
```
### queue.c
* q_new
* 使用 `malloc()` 配置記憶體，並且初始所有的變數。
* 需要注意在 `malloc()` 失敗時要回傳 `NULL` 。
* q_free
* 因為每個 queue 的節點中都有一個指向字串的指標，所以在處理時必須先釋放掉字串的記憶體，再釋放節點的記憶體。
* 確認所有節點都被釋放掉後，最後則是將 queue 本身佔用的記憶體釋放掉。
* q_insert_head
* 配置節點的記憶體，並且依照傳入字串的大小配置字串的記憶體，最後使用 `strcpy()` 將字串內容複製過去。
* 如果 queue 本來就還沒建立，或者配置記憶體沒有成功，則回傳 `false` 。
* 建立完節點之後，要讓這個節點的 `next` 先指向原本的 `head` ，再將 queue 的 `head` 指向這個節點。
* 加入新的節點後，將 queue 的 `size` 增加 1 ，並且回傳 `true` 。
* 需要特別注意在配置記憶體失敗時要回傳 `NULL` ，尤其是配置字串的記憶體失敗時，還要記得把先前配置給節點的記憶體也釋放掉。
* 時間複雜度： $O(1)$
* q_insert_tail
* 因為我們有新增一個指標 `tail` 指向 queue 的末端，大致內容與 `q_insert_head()` 一樣，只是建立完節點之後要先讓原本的 `tail->next` 指向新增的節點，再讓 queue 的 `tail` 指向新節點。
* 時間複雜度： $O(1)$
* q_remove_head
* 先確認 queue 是否有建立以及 queue 是否是空的，如果是空的直接回傳 `false` 。
* 先使用 `memset()` 將 `sp` 的內容全部初始為 `\0 ` 後，在將 `head` 所指到的節點的字串使用 `strncpy()` 複製到 `sp` ，以避免超過 `bufsize` 。
* 最後先用一個指標存下目前 `head` 的位址，然後將 `head` 指向下一個節點後，把指標所指的節點的字串以及本身的記憶體釋放掉。
* 刪除節點後，將 queue 的 `size` 減少 1 ，並且回傳 `true` 。
* 時間複雜度： $O(1)$
* q_size
* 因為在 queue 中插入或刪除資料時都會更新 `size` 的大小，所以除非 queue 本身沒有建立時要直接回傳 0 之外，都可以直接回傳 queue 中記錄的 `size` 。
* 時間複雜度： $O(1)$
* q_reverse
* 如果 queue 還沒建立，或者 queue 的 `size` 小於等於 1 時，就直接 return 。
* 為了要實現在不新增節點的情況下將 queue 顛倒過來，利用了三個指標 `last` 、 `curr` 、 `next` 指向三個連續的節點，來將 `curr` 中所指的下一個節點從 `next` 改為 `last` ，並且不斷將全部的指標移往下一個節點。
* 最後要交換 `head` 及 `tail` ，讓指標正確指向 queue 的頭尾端。
* 時間複雜度： $O(n)$
## 評分結果
```shell
$ make test
scripts/driver.py
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
--- trace-05-ops 6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
--- trace-15-perf 7/7
--- TOTAL 100/100
```
## 自動評分系統運作原理
從 Makefile 中可以得知，執行 `$ make test` 時實際上就是執行 scripts/driver.py 這個程式。
```bash
test: qtest scripts/driver.py
scripts/driver.py
```
透過執行 `$ scripts/driver.py -h` 可以看到有許多參數可以調整。
```shell
$ scripts/driver.py -h
Usage: scripts/driver.py [-h] [-p PROG] [-t TID] [-v VLEVEL]
-h Print this message
-p PROG Program to test
-t TID Trace ID to test
-v VLEVEL Set verbosity level (0-3)
```
其中 TID 表示要使用哪一筆測試資料，預設的 TID 為 0 ，用來表示要使用所有的測試資料； verbosity level 則表示執行時所印出的訊息的多寡程度，以下利用了第一筆測試資料來實驗不同 verbosity level 的差異：
```shell
$ scripts/driver.py -t 1 -v 0
--- Trace Points
--- trace-01-ops 6/6
--- TOTAL 6/6
```
```shell
$ scripts/driver.py -t 1 -v 1
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
--- TOTAL 6/6
```
```shell
$ scripts/driver.py -t 1 -v 2
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
cmd>ih gerbil
cmd>ih bear
cmd>ih dolphin
cmd>rh dolphin
Removed dolphin from queue
cmd>rh bear
Removed bear from queue
cmd>rh gerbil
Removed gerbil from queue
cmd>
--- trace-01-ops 6/6
--- TOTAL 6/6
```
```shell
$ scripts/driver.py -t 1 -v 3
--- Trace Points
+++ TESTING trace trace-01-ops:
cmd># Test of insert_head and remove_head
cmd>option fail 0
cmd>option malloc 0
cmd>new
q = []
cmd>ih gerbil
q = [gerbil]
cmd>ih bear
q = [bear gerbil]
cmd>ih dolphin
q = [dolphin bear gerbil]
cmd>rh dolphin
Removed dolphin from queue
q = [bear gerbil]
cmd>rh bear
Removed bear from queue
q = [gerbil]
cmd>rh gerbil
Removed gerbil from queue
q = []
cmd>
Freeing queue
--- trace-01-ops 6/6
--- TOTAL 6/6
```
可以看出當 verbosity level 為 0 時只會印出分數，為 1 的時候會印出測試的項目，為 2 會印出執行的每一個指令，為 3 時則會將執行完每一個指令後的 queue 的內容一起印出。
處理完輸入的參數後， scripts/driver.py 接下來就會依此去執行 qtest ，讓 qtest 從 trace 資料夾中讀取相對應的 .cmd 檔來測試。
```python=
def runTrace(self, tid):
if not tid in self.traceDict:
print "ERROR: No trace with id %d" % tid
return False
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
return retcode == 0
```
第 9 行的 [`subprocess.call()`](https://docs.python.org/2/library/subprocess.html#using-the-subprocess-module) 是 python 中增加子行程的函式，可以直接執行外部程式並且加上執行時需要的命令列參數，直到外部程式結束後回傳 return code 。
觀察以上整段 `runTrace()` 後可以發現只有當 qtest 回傳的 `retcode` 等於 `0` 的時候，整個函式才有可能回傳 `True`，並且存在下面 `run()` 函式第 7 行的 `ok` 中。
```python=
def run(self, tid = 0):
...
score = 0
...
for t in tidList:
...
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
...
score += tval
...
```
又因為只有當 `ok` 為 `True` 時才能得到整題的分數 `maxval` ，我們可以推論是否能得到分數完全取決於 qtest 最後的回傳值是否等於 `0` 。
## qtest 的行為與技巧
在 harness.h 中有以下的程式碼，將原本 C 語言定義的函式 `malloc()` 與 `free()` 重新定義到 `test_malloc()` 與 `test_malloc()` 。
```css
/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_malloc
```
其中 `test_malloc()` 會呼叫 `fail_allocation()` 這個函式，並依據當前的 malloc 失敗機率 `fail_probability` 決定這次配置記憶體是否成功。
```C=
/* Should this allocation fail? */
static bool fail_allocation()
{
double weight = (double) random() / RAND_MAX;
return (weight < 0.01 * fail_probability);
}
```
在 harness.c 中可以發現，實際上所有透過 `test_malloc()` 配置的記憶體會使用以下的資料結構存成一個 doubly-linked list。
```C=
typedef struct BELE {
struct BELE *next;
struct BELE *prev;
size_t payload_size;
size_t magic_header; /* Marker to see if block seems legitimate */
unsigned char payload[0];
/* Also place magic number at tail of every block */
} block_ele_t;
```
這裡的 `payload[0]` 是一個長度為零的陣列，放在 struct 的最後面，可以用來標示其後所接的記憶體的起始位置。
```C=
void *test_malloc(size_t size)
{
...
block_ele_t *new_block =
malloc(size + sizeof(block_ele_t) + sizeof(size_t));
...
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
...
return p;
}
```
上面第四行的程式碼顯示，我們實際上配置的記憶體大小是由 `block_ele_t` 加上我們原本要配置的記憶體大小 `size` ，以及一個 footer 所組成。
因此我們以為用 `malloc()` 配置到的一整塊記憶體實際上是跟在一個 `block_ele_t` 的 struct 後面，並且最後還跟著一個 footer，而且從第十行程式碼可以看到 `test_malloc()` 回傳的指標 `p` 就是指向 payload 所在的位址。
```C=
void test_free(void *p)
{
...
block_ele_t *b = find_header(p);
...
/* Unlink from list */
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
free(b);
allocated_count--;
}
```
與 `test_malloc()` 相對應的，使用 `test_free()` 時則會先呼叫 `find_header()` ，並且如以下的程式碼所示，減掉 `block_ele_t` 的大小來往前找到當初宣告記憶體的起始位址，之後會再對 doubly-linked list 的指標進行操作後，把整塊配置的記憶體釋放掉。
```C=
static block_ele_t *find_header(void *p)
{
...
block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));
...
return b;
}
```
Sign in with Wallet
Connect another wallet