2019q3 Homework2 (lab0)

contributed by < uccuser159 >

開發環境

作業系統：Ubuntu 18.04.2 LTS

---

Overview

• 在 C Programming Lab 中要使用 Linked list 來實作 Queue
  在queue.h 有宣告兩個結構：

/* Linked list element */
typedef struct ELE {
    char *value;
    struct ELE *next;
} list_ele_t;

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
} queue_t;

value 會指向字串的一個指標
next 會指向下一個 linked-list
head 為 queue 中的第一個 linked-list

定義 NULL queue 和 empty queue ：
NULL queue 表示沒有 queue
empty queue 表示的是一個空的 queue

在queue.c中要執行下列這些 task：

• q_new：製造出一個新的 queue (empty queue)
• q_free：將 queue 所佔的記憶體給釋放掉
• q_insert_head : 在 queue 的 head 插入元素( LIFO )
• q_insert_tail : 在 queue 的 tail 插入元素( FIFO )
• q_remove_head : 從 queue 的 head 移除元素
• q_size : 回傳目前 queue 的大小
• q_reverse : 把 queue 做反轉

---

實作

• 為了確認 q_insert_tail 和 q_size 的時間複雜度為
  $O(1)$ ，所以在queue.h中加入指向 queue 尾端的 pointer 以及儲存 size 大小。

typedef struct {
    list_ele_t *head; 
    list_ele_t *tail;
    int size;
} queue_t;

• q_new

queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
        return NULL;

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

• q_free

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

    /* Free queue structure */
    free(q);
}

• q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (q == NULL)
        return false;

    newh = malloc(sizeof(list_ele_t));
    /* Don't forget to allocate space for the string and copy it */
    char *add = malloc((strlen(s) + 1) * sizeof(char));

    /* What if either call to malloc returns NULL? */
    if (newh == NULL || add == NULL) {
        free(newh);
        free(add);
        return false;
    }
    strcpy(add, s);
    newh->value = add;
    newh->next = q->head;
    q->size = q->size + 1;
    if (q->head == NULL)  // first insert
        q->tail = newh;
    q->head = newh;
    return true;
}

• q_insert_tail

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

• q_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;

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

    list_ele_t *replace;

    replace = q->head;
    q->head = q->head->next;
    free(replace->value);
    free(replace);
    q->size = q->size - 1;
    return true;
}

• q_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 == NULL)
        return 0;
    return q->size;
}

• q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0 || q->size == 1)
        return;
    list_ele_t *cur = q->head->next;
    q->head->next = NULL;
    list_ele_t *temp;

    q->tail = q->head;
    while (cur != NULL) {
        temp = cur->next;
        cur->next = q->head;
        q->head = cur;
        cur = temp;
    }

---

自動評分運作

• 由於是執行make test指令來跑評分系統，所以進入 Makefile 檔中的test部分：

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

可以得知進行自動評分，需要scripts/driver.py來執行qtest。

• 往scripts/driver.py看：

    traceDirectory = "./traces"
    qtest = "./qtest"
    command = qtest
    verbLevel = 0
    autograde = False
    useValgrind = False

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

    optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])
    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
        elif opt == '--valgrind':
            useValgrind = True
        else:
            print("Unrecognized option '%s'" % opt)
            usage(name)
    if not levelFixed and autograde:
        vlevel = 0
    t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
    t.run(tid)

在optlist, args = getopt.getopt(args, 'hp:t:v:A', ['valgrind'])中：

• getopt.getopt 回傳的是兩個陣列： optlist 和 args ： optlist是分析出的格式，而 args 為不屬於格式訊息的剩下參數。
• 'hp:t:v:A' 此處為短選項。沒有" : "的短選項就像一個開關，若有在 optlist 中有回傳此格式即觸發；而有" : "的短選項表示後面帶一個參數 arg。
• ['valgrind'] 此處為長選項。沒有" = "的長選項就像一個開關，若有在 optlist 中有回傳此格式即觸發；而有" = "的長選項表示後面帶一個參數 arg。

在if條件式中有各項功能。

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
        elif opt == '--valgrind':
            useValgrind = True
        else:
            print("Unrecognized option '%s'" % opt)
            usage(name)

在函式usage(name)中有個短選項的各項功能，而['valgrind']這個長選項是在決定useValgrind功能要不要開啟：

def usage(name):
    print("Usage: %s [-h] [-p PROG] [-t TID] [-v VLEVEL] [--valgrind]" % 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)

最後在呼叫Tracer這個 class，來做自動評分：

t = Tracer(qtest = prog, verbLevel = vlevel, autograde = autograde, useValgrind = useValgrind)
t.run(tid)

• Reference
  -sys.argv和getopt.getopt()的用法
  -Makefile語法和示範

---

qtest 的 signal handler

• C99規格書
  • 7.14中提到 signal 是 conditions that may be reported during program execution.

7.14.1 Synopsis

#include <signal.h>
void (*signal(int sig, void (*func)(int)))(int);

7.14.2 Description
The signal function chooses one of three ways in which receipt of the signal number sig is to be subsequently handled. If the value of func is SIG_DFL, default handling for that signal will occur. If the value of func is SIG_IGN, the signal will be ignored. Otherwise, func shall point to a function to be called when that signal occurs. An invocation of such a function because of a signal, or (recursively) of any further functions called by that invocation (other than functions in the standard library), is called a signal handler.

/* Signal handlers */
void sigsegvhandler(int sig)
{
    trigger_exception(
        "Segmentation fault occurred.  You dereferenced a NULL or invalid "
        "pointer");
}

void sigalrmhandler(int sig)
{
    trigger_exception(
        "Time limit exceeded.  Either you are in an infinite loop, or your "
        "code is too inefficient");
}

static void queue_init()
{
    fail_count = 0;
    q = NULL;
    signal(SIGSEGV, sigsegvhandler);
    signal(SIGALRM, sigalrmhandler);
}

• SIGALRM : Time limit exceeded

在harness.h中有exception_setup . exception_cancel . trigger_exception三個函式：

bool exception_setup(bool limit_time)
{
    if (sigsetjmp(env, 1)) {
        /* Got here from longjmp */
        jmp_ready = false;
        if (time_limited) {
            alarm(0);
            time_limited = false;
        }
        if (error_message) {
            report_event(MSG_ERROR, error_message);
        }
        error_message = "";
        return false;
    } else {
        /* Got here from initial call */
        jmp_ready = true;
        if (limit_time) {
            alarm(time_limit);
            time_limited = true;
        }
        return true;
    }
}

void exception_cancel()
{
    if (time_limited) {
        alarm(0);
        time_limited = false;
    }
    jmp_ready = false;
    error_message = "";
}

void trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

• sigsetjmp(sigjmp_buf env, int savemask) 會保存目前 stack ，然後將目前的地址記錄起來，而在其他函數用 siglongjmp() 時便會直接跳到所記錄的位址，還原 stack ，再繼續執行其他函式。
  env : A buffer where the function can save the calling environment.
  savemask : Nonzero if you want to save the process's current signal mask, otherwise 0.
• alarm(unsigned int seconds) 當呼叫了alarm(n)後，等待n秒後，就會觸發一次的SIGALRM的signal，如果 alarm 的參數 seconds 為0，則之前設置的 Timer 會被取消，並將剩下的時間返回。

所以bool exception_setup(bool limit_time) 是用來判別程序執行時是否超過指定時間( time_limit = 1)。

• [ ]若超過時間：
  jmp_ready == true → 呼叫trigger_exception儲存錯誤訊息( error_message )且將 error_occurred 設成 true → 由 siglongjmp 返回 exception_setup 進入 if 迴圈 重新計時且顯示錯誤訊息，最後回傳false。
• [ ]若沒有超過時間：
  time_limited == true→ 呼叫exception_cancel重新計時且將jmp_ready設回 false ， error_message 也設為空白字元使其不顯示