2019q1 Homework1 (lab0)

contributed by < TWPLrh >

系統環境

Linux shihruhung-pc 4.18.0-15-generic #16-Ubuntu SMP Thu Feb 7 10:56:39 
UTC 2019 x86_64 x86_64 x86_64 GNU/Linux

gcc (Ubuntu 8.2.0-7ubuntu1) 8.2.0

作業要求

完成 Queue 程式碼

• struct queue_t - 增加tail和size已達到O(1)。

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

• q_new - 新建 Queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
        
    if (!q)
        return NULL;

    q->size = 0;
    q->head = q->tail = NULL;

    return q;
}

照著註解去做，如果沒分配到的話要return NULL，如果成功，就必須設定初始值之後回傳。

• q_free - 釋放 Queue

void q_free(queue_t *q)
{
    if (!q)
        return;

    list_ele_t *prev;

    while (q->head) {
        prev = q->head;
        q->head = q->head->next;

        if (prev->value)
            free(prev->value);
        free(prev);
    }

    free(q);
}

當q->head不是null，就將q->head移到next，並將prev的value和prev釋放。

• q_insert_head - 插入 Queue

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    newh->value = strcpy(newh->value, s);

    q->size += 1;

    if (q->size == 1) {
        q->head = q->tail = newh;
        q->head->next = NULL; 
    } else {
        newh->next = q->head;
        q->head = newh;
    }

    return true;
}

這裡的重點我認為是在Size=1時如果不將newh->next設成null，在make test時就會說錯誤，這也讓我意識到，C在malloc後並不會將所有初值都弄好，需要用memset去清空或是每個property依次去設定。

• q_insert_tail - 插入 Queue 尾端

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }

    newh->value = strcpy(newh->value, s);

    q->size += 1;
    newh->next = NULL;

    if (q->size == 1)
        q->head = q->tail = newh;
    else {
        q->tail->next = newh;
        q->tail = newh;
    }

    return true;
}

和q_insert_head差不多，不一樣的地方在line 20之後，q->tail->next一定是null所以可以不用包在if裡面，else的話則先把q->tail->next設爲newh，再把q->tail設爲newh這是和q_insert_head不同的地方。

• q_remove_head - 移除 Queue Head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !q->head || q->size == 0)
        return false;

    if (sp) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_ele_t *next = q->head->next;

    q->size -= 1;
    if (q->head->value)
        free(q->head->value);
    free(q->head);

    if (q->size == 0)
        q->head = q->tail = NULL;
    else
        q->head = next;

    return true;
}

照著註解要求，先把會false的情況寫在前面，之後就代表這個Queue是可以被remove_head，再確認sp是否non-null，如果是，就複製過去，並把bufsize-1設成'\0'，再做一些property的修改即可。

• q_size - 回傳 Queue Size

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)
        return 0;

    return q->size;
}

直接回傳Queue的size，如果null，回傳0

• q_reverse - 前後翻轉 Queue 的順序

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q && q->size != 0) {
        q->tail = q->head;
        list_ele_t *prev = NULL, *next;

        while (q->head) {
            next = prev;
            prev = q->head;
            q->head = q->head->next;
            prev->next = next;
        }
        q->head = prev;
    }
}

翻轉就只是簡單的改變list方向而已，方法如code所示，先把q->tail設爲q->head
，loop裡面就是將list前後串接改變，第一次是null，最後因為q->head已經指到不知道什麼地方，所以把他指回prev

自動評分系統

Usage : make test

Tracing 過程

• makefile -> qtest.c -> script/driver.py -> traces/

makefile

• makefile 中有 test，當在terminal輸入 make test時即會呼叫test下的scripts/driver.py來協助評分和輸出。

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

qtest.c

• qtest.c 的 console_init()，把測試的function都加入且綁定到cmd上，綁定的function都有各種條件來測試記憶體是否釋放以及邏輯是否造成運行上的錯誤。錯誤會呼叫report()來印出那裡有錯及錯誤類別。

static void console_init(){...}

script/driver.py

• script/driver.py 有 class Tracer 目的在執行15種trace方法，當每個方法都run過之後會印出總分。執行每一種執行方法都會呼叫trace\目錄下的*.cmd，並利用subprocess.call()執行qtest下的測試函式。

traces/

• trace/ 下的檔案都是執行測試的腳本，對應的就是qtest.c下console_init()所加入cmd的函式。