# 2018q3 Homework2(lab0)
contributed by <[`datuiji`](https://github.com/datuiji/lab0-c)>
## 實驗環境

NAME="Ubuntu"
VERSION="16.04.5 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.5 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial

## 實驗結果

---     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

## 開發紀錄
### queue.h

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size; /*
      You will need to add more fields to this structure
      to efficiently implement q_size and q_insert_tail
     */
} queue_t;

- 在queue.h中，新增了 tail 指標與 int size，新增 tail 指標原因是為了紀錄 queue 的 tail ，如此才能實做 bool q_queue_tail(queue_t *q,char *s) 在 O(1) 時間內，而新增 int size 是因為能夠實做 int q_size(queue_t *q) 在 O(1) 時間內。
### queue_t *q_new()

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL) {
        return NULL;
    } else {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
        return q;
    }
}

- 此處因為做了 malloc 所以必須考慮到 malloc 是否成功，如果失敗則回傳 NULL 。
### q_free()

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if (q == NULL) {
        return;
    } else {
        while (q->head) {
            list_ele_t *temp = q->head;
            free(temp->value);
            q->head = q->head->next;
            free(temp);
        }
    }

- 在這個函式中，功能為刪除整個 queue ，所以需要拜訪完整個 queue 並 free 節點與它的數值。
### bool q_insert_head(queue_t *q, char *s)

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL) {
        return false;
    } else {
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if (newh == NULL) {
            return false;
        } else {
            newh->value = malloc(sizeof(char) * (strlen(s) + 1));
            if (newh->value == NULL) {
                free(newh);
                return false;
            }
            strcpy(newh->value, s);
            if (q->head == NULL) {
                q->head = newh;
                q->tail = newh;
                newh->next = NULL;
            } else {
                newh->next = q->head;
                q->head = newh;
            }
            q->size++;
            return true;
        }
    }
}

- 實作邏輯為：
- 先 malloc 記憶體給欲插入節點的數值，之後判斷 malloc 是否成功，再來將新節點的數值 s 複製給剛 malloc 的記憶體空間，之後移動指標，如果插入 queue 還沒有節點，就把新節點設為 head 與 tail 否則將新節點加入 queue 中，並移動指標。
- 在處理這函式的時候一開使用的是 strdup 。

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if(q == NULL){
        return false;
    }
    else{
        /* Don't forget to allocate space for the string and copy it */
        /* What if either call to malloc returns NULL? */
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if(newh == NULL){
            return false;
        }
        else{
            newh->value = strdup(s);
            if(q->head == NULL){
                q->head = newh;
                q->tail = newh;
                newh->next = NULL;
            }
            else{
                newh->next = q->head;
                q->head = newh;
            }
            q->size++;
            return true;
        }
        
    }
    
}

- 導致以下錯誤：

+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Attempted to free unallocated block.  Address = 0xc56500
ERROR: Attempted to free unallocated or corrupted block.  Address = 0xc56500
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (1 failures total)
ERROR: Attempted to free unallocated block.  Address = 0xc56520
ERROR: Attempted to free unallocated or corrupted block.  Address = 0xc56520
ERROR: Corruption detected in block with address 0xc56520 when attempting to free it
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (2 failures total)
ERROR: Attempted to free unallocated block.  Address = 0xc56560
ERROR: Attempted to free unallocated or corrupted block.  Address = 0xc56560
ERROR: Corruption detected in block with address 0xc56560 when attempting to free it
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (3 failures total)
---     trace-01-ops    0/6

- 在函式中用了 strdup 所以 free 時造成以上錯誤，這邊不能使用 strdup 原因是因為原本使用 strdup 是用了原本 c 語言定義的 malloc 與 free，而在這個 harness.h 中已經把 malloc 重新定義為 *test_malloc 而 free 重新定義為 test_free 。
### bool q_insert_tail(queue_t *q, char *s)

bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return false;
    } else {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if (newh == NULL) {
            return false;
        } else {
            newh->value = malloc(sizeof(char) * (strlen(s) + 1));
            if (newh->value == NULL) {
                free(newh);
                return false;
            }
            strcpy(newh->value, s);
            if (q->head == NULL) {
                q->head = newh;
                q->tail = newh;
                newh->next = NULL;
            } else {
                q->tail->next = newh;
                q->tail = newh;
                newh->next = NULL;
            }
            q->size++;
            return true;
        }
    }
}

- 在實作 insert_tail 這個函式沒什麼問題，因為邏輯跟insert_head差不多。
### bool q_remove_head(queue_t *q, char *sp, size_t bufsize)

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0) {
        return false;
    } else {
        list_ele_t *temp = q->head;
        q->head = q->head->next;
        if (sp != NULL) {
            memset(sp, '\0', bufsize);
            strncpy(sp, temp->value, bufsize - 1);
        }
        free(temp->value);
        free(temp);
        q->size--;
        if (q->size == 0) {
            q->tail = NULL;
        }
        return true;
    }
}

- 實作邏輯為：先判斷 queue 是否有節點，如果沒有節點做 remove head 就會回傳失敗，否則先宣告一個暫存節點，把欲刪除節點的數值存到 sp 中，之後陸續把欲刪除節點之數值與節點本身 free 掉。
- 在實作 remove head 時，我一開始用了下列方法：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if(q == NULL || q->size == 0){
        return false;
    }
    else{
        list_ele_t *temp = q->head;
        if(temp->value != NULL){
            strncpy(sp, temp->value, bufsize);
            free(temp->value);
        }
        q->head = q->head->next;
        free(temp);
        q->size--;
        if(q->size == 0){
            q->tail = NULL;
        }
        return true;
    }
}

- 造成以下錯誤：

+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR:  Removed value meerkat_panda_squirrel_vulture_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel_vulture
ERROR:  Removed value aardvark_bear_dolphin_gerbil_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin_gerbil
ERROR:  Removed value aardvark_bear_dolphin_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value aardvark_bear_dolphin
ERROR:  Removed value meerkat_panda_squirrel_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat_panda_squirrel
ERROR:  Removed value meerkat_XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX != expected value meerkat
Error limit exceeded.  Stopping command execution
---     trace-06-string 0/7

- 後來找到在 if(temp->value != NULL) 這個判斷時出錯，因為改用 if (sp != NULL) 邏輯才合理，且以下動作改成 memset 先初始化 sp 為 '\0' 然後在用 strncpy 將節點數值複製到 sp ，最後把節點數值跟節點本身 free 掉，這樣就成功了。
### int q_size(queue_t *q)

int q_size(queue_t *q)
{
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return 0;
    } else {
        return q->size;
    }
}

- 因為在前面的函式中都有紀錄 q->size 所以在此函式中就只需要回傳 q->size。

### void q_reverse(queue_t *q)

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->size == 0) {
        return;
    }
    list_ele_t *pre = NULL;
    list_ele_t *cur = q->head;
    list_ele_t *next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    q->tail = q->head;
    q->head = pre;
    return;
}

- 實作 reverse 我用了三個指標來達到此目的，並參考此篇作法：https://www.youtube.com/watch?v=oVd1uAZ6Q4U&ab_channel=%E9%99%B3%E9%8C%A6%E8%BC%9D 。

## 自動評分系統運作的原理
- [Makefile 參考資料](http://mropengate.blogspot.com/2018/01/makefile.html)
- Makefile

CC = gcc
CFLAGS = -O0 -g -Wall -Werror

GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest

$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

queue.o: queue.c queue.h harness.h
	$(CC) $(CFLAGS) -c queue.c 

qtest: qtest.c report.c console.c harness.c queue.o
	$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

test: qtest scripts/driver.py
	scripts/driver.py

clean:
	rm -f *.o *~ qtest 
	rm -rf *.dSYM
	(cd traces; rm -f *~)

- 在 Makefile 中發現當執行 make test 時會執行 scripts/driver.py 所以只要知道 driver.py 的功能就知道自動評分系統如何運作。
- driver.py

#!/usr/bin/python

import subprocess
import sys
import getopt

# Driver program for C programming exercise
class Tracer:
    
    traceDirectory = "./traces"
    qtest = "./qtest"
    verbLevel = 0
    autograde = False

    traceDict = {
        1 : "trace-01-ops",
        2 : "trace-02-ops",
        3 : "trace-03-ops",
        4 : "trace-04-ops",
        5 : "trace-05-ops",
        6 : "trace-06-string",
        7 : "trace-07-robust",
        8 : "trace-08-robust",
        9 : "trace-09-robust",
        10 : "trace-10-malloc",
        11 : "trace-11-malloc",
        12 : "trace-12-malloc",
        13 : "trace-13-perf",
        14 : "trace-14-perf",
        15 : "trace-15-perf"
        }

    traceProbs = {
        1 : "Trace-01",
        2 : "Trace-02",
        3 : "Trace-03",
        4 : "Trace-04",
        5 : "Trace-05",
        6 : "Trace-06",
        7 : "Trace-07",
        8 : "Trace-08",
        9 : "Trace-09",
        10 : "Trace-10",
        11 : "Trace-11",
        12 : "Trace-12",
        13 : "Trace-13",
        14 : "Trace-14",
        15 : "Trace-15"
        }


    maxScores = [0, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7]

    def __init__(self, qtest = "", verbLevel = 0, autograde = False):
        if qtest != "":
            self.qtest = qtest
        self.verbLevel = verbLevel
        self.autograde = autograde

    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

    def run(self, tid = 0):
        scoreDict = { k : 0 for k in self.traceDict.keys() }
        print("---\tTrace\t\tPoints")
        if tid == 0:
            tidList = self.traceDict.keys()
        else:
            if not tid in self.traceDict:
                print("ERROR: Invalid trace ID %d" % tid)
                return
            tidList = [tid]
        score = 0
        maxscore = 0
        for t in tidList:
            tname = self.traceDict[t]
            if self.verbLevel > 0:
                print("+++ TESTING trace %s:" % tname)
            ok = self.runTrace(t)
            maxval = self.maxScores[t]
            tval = maxval if ok else 0
            print("---\t%s\t%d/%d" % (tname, tval, maxval))
            score += tval
            maxscore += maxval
            scoreDict[t] = tval
        print("---\tTOTAL\t\t%d/%d" % (score, maxscore))
        if self.autograde:
            # Generate JSON string
            jstring = '{"scores": {'
            first = True
            for k in scoreDict.keys():
                if not first:
                    jstring += ', '
                first = False
                jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
            jstring += '}}'
            print(jstring)

def usage(name):
    print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL]" % name)
    print("  -h        Print this message")
    print("  -p PROG   Program to test")
    print("  -t TID    Trace ID to test")
    print("  -v VLEVEL Set verbosity level (0-3)")
    sys.exit(0)

def run(name, args):
    prog = ""
    tid = 0
    vlevel = 1
    levelFixed = False
    autograde = False
    

    optlist, args = getopt.getopt(args, 'hp:t:v:A')
    for (opt, val) in optlist:
        if opt == '-h':
            usage(name)
        elif opt == '-p':
            prog = val
        elif opt == '-t':
            tid = int(val)
        elif opt == '-v':
            vlevel = int(val)
            levelFixed = True
        elif opt == '-A':
            autograde = True
        else:
            print("Unrecognized option '%s'" % opt)
            usage(name)
    if not levelFixed and autograde:
        vlevel = 0
    t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde)
    t.run(tid)

if __name__ == "__main__":
    run(sys.argv[0], sys.argv[1:])

- 當在 command line 輸入 make test 就會開始執行 run 函式執行自動測試，另外還有一個功能就是可以獨立測試15個 trace 。
## qtest 的行為和裡頭的技巧
- 當我們輸入 ./qtest 時，command line 會出現 cmd ，此時就可以開始輸入測資開始測試，所以我很好奇這項功能如何工作。打開 qtest.c 可以看見 static void console_init() 這個函式主要是讓我們能輸入測資進行測試，但在 qtest.c 中我找不到 add_cmd 的函式，於是我 google 一下發現這是運用 GDB 的技巧，透過此項功能可以讓我們更容易去除錯。

2.5.  Adding Commands to GDB
As noted in Section 2.2, GDB's command handling is extensible. Commands are grouped into a number of command lists (of type struct cmd_list_element), pointed to by a number of global variables (defined in cli-cmds.h). Of these, cmdlist is the list of all defined commands, with separate lists defined for sub-commands of various top level commands. For example infolist is the list of all info sub-commands.

Each command (or sub-command) is associated with a callback function which implements the behavior of the functions. There are additional requirements for functions which set or show values within GDB. Each function also takes a documentation string (used by the help command). Functions for adding commands all return a pointer to the struct cmd_list_element for the command added (which is not necessarily the head of its command list). The most useful functions are:

add_cmd. Add a function to a command list.

add_com. Add a function to the main command list, cmdlist. This is a convenience wrapper for add_cmd.

add_prefix_cmd. Add a new prefix command. This command should have its own function for use if it is called on its own, and a global command list pointer specific to the prefix command to which all its sub-commands will be added. If a prefix command is called with an unknown sub-command, it can either give an error or call the function of the prefix command itself. Which of these is used is specified by a flag in the call to add_prefix_cmd.

add_alias_cmd. Add an alias for a command already defined.

add_info. Add a sub-command to the info. A convenience wrapper for add_cmd.

New commands are usually added in the _initialize_arch function after the struct gdbarch has been defined.

static void console_init()
{
    add_cmd("new", do_new, "                | Create new queue");
    add_cmd("free", do_free, "                | Delete queue");
    add_cmd("ih", do_insert_head,
            " str [n]        | Insert string str at head of queue n times "
            "(default: n == 1)");
    add_cmd("it", do_insert_tail,
            " str [n]        | Insert string str at tail of queue n times "
            "(default: n == 1)");
    add_cmd("rh", do_remove_head,
            " [str]          | Remove from head of queue.  Optionally compare "
            "to expected value str");
    add_cmd(
        "rhq", do_remove_head_quiet,
        "                | Remove from head of queue without reporting value.");
    add_cmd("reverse", do_reverse, "                | Reverse queue");
    add_cmd("size", do_size,
            " [n]            | Compute queue size n times (default: n == 1)");
    add_cmd("show", do_show, "                | Show queue contents");
    add_param("length", &string_length, "Maximum length of displayed string",
              NULL);
    add_param("malloc", &fail_probability, "Malloc failure probability percent",
              NULL);
    add_param("fail", &fail_limit,
              "Number of times allow queue operations to return false", NULL);
}

## 參考資料
- [GNU debugger](https://www.embecosm.com/appnotes/ean3/embecosm-howto-gdb-porting-ean3-issue-2.html)