changed 7 years ago  
Linked with GitHub

2018q3 Homework2

contributed by <jesus255221>

請補上實驗環境
課程助教

實驗環境

OS: Linux Ubuntu 18.04 64位元
CPU: Intel E3 1230V2
MEM: 20GB DDR3

關於常數時間的考慮










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

作業要求必須要常數時間完成 size 的存取與 tail 的插入。很直覺的就是用空間換取時間。即



    int q_size;       //The size of q
    list_ele_t *tail; //The tail of q

malloc失敗的考慮

以下節錄自 linux man page

The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

也就是說當 malloc 失敗時，將會回傳NULL。
程式碼裡面也多處檢查是否為 NULL pointer，這便是巨集使用的好時機。





#define NULL_CHECK(condition) \
    if (!condition) {         \
        return false;         \
    }

只要當condition為NULL時，便會回傳false。可用於會回傳bool型態的函數。

q_new













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

一開始先做malloc檢查，成功以後將 head, tail, q_size初始化。

q_free

















void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    if(!q){
        return;
    }
    /* Free queue structure */
    list_ele_t *current_ptr = q->head, *prev;
    while (current_ptr != NULL) {
        free(current_ptr->value);         // Free the current string
        prev = current_ptr;               // Save the previous list node
        current_ptr = current_ptr->next;  // Go to the next node
        free(prev);                       // free the previous node
    };
    free(q);
}

一樣先檢查q是否為NULL，再處理記憶體釋放。
創建兩個指標用於走訪 list
直到目前指標等於NULL時再停下，不然就持續走訪每個節點。
釋放字串所用的空間之後把目前 pointer 指到下個節點，再把上個節點的空間釋放。

q_reverse






















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

    while (current) {
        next = current->next; // Point to the next node
        current->next = prev; // Point the next pointer of current pointer to the previous one
        prev = current; // Point the previous pointer to the current pointer
        current = next; // Point the current pointer to the next pointer
    }
    current = q->head; // Reverse the head and tail
    q->head = q->tail;
    q->tail = current;

    return;
}

一樣先檢查q是否為NULL。準備三個指標，*prev, *current, *next，當目前的指標不是NULL時，把目前指標的 next 指向上一個 node。如此直到 current pointer 為NULL 為止。最後再 exchange head and tail

q_insert_head, q_insert_tail































































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 */
    list_ele_t *newt;
    NULL_CHECK(q);
    newt = malloc(sizeof(list_ele_t));
    NULL_CHECK(newt);

    newt->value = malloc(strlen(s) + 1);

    if (!newt->value) {
        free(newt);
        return false;
    }

    strcpy(newt->value, s);
    newt->value[strlen(s)] = '\0';
    newt->next = NULL;

    // If this node is the first node
    if (!q->q_size) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    q->tail = newt;
    q->q_size++;
    return true;
}


bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    NULL_CHECK(q);
    newh = malloc(sizeof(list_ele_t));
    NULL_CHECK(newh);
    /* Don't forget to allocate space for the string and copy it */
    // malloc string size plus the terminating character
    newh->value = malloc(strlen(s) + 1);

    /* What if either call to malloc returns NULL? */
    /* If malloc failed... */
    if (!newh->value) {
        free(newh);
        return false;
    }

    // Copy the string
    strcpy(newh->value, s);
    newh->value[strlen(s)] = '\0';
    /* If this is the first node in the list, set the tail to it*/
    if (!q->q_size) {
        q->tail = newh;
    }
    newh->next = q->head;
    q->head = newh;
    q->q_size++;
    return true;
}

q_insert_head 與 q_insert_tail 的實作非常類似。一開始先檢查 q 是否為 NULL，之後再malloc新的記憶體給新的節點並且檢查是否成功。確認成功之後再配置節點內字串所需記憶體，再利用系統函數strcpy來複製字串，最後再將節點插入 queue 中並且進行相對應的節點更動。

q_remove_head



























bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    NULL_CHECK(q);
    NULL_CHECK(q->head);
    if (sp) {
        if (strlen(q->head->value) >= (bufsize - 1)) {
            strncpy(sp, q->head->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        } else {
            strncpy(sp, q->head->value, strlen(q->head->value));
            sp[strlen(q->head->value)] = '\0';
        }
    }
    free(q->head->value);
    list_ele_t *head;
    head = q->head;
    q->head = q->head->next;
    q->q_size--;

    if (!q->q_size) {
        q->tail = NULL;
    }
    free(head);
    return true;
}

q_remove_head應該算是裡面比較複雜的函數了，一開始必須檢查是否是 quiet removal，也就是sp是否為NULL，之後再判斷真正字串的長度是否有比bufsize大。是，則複製 bufsize - 1 的字串(因為最後面要放'\0')。否，則複製字串長度的資料就好。
之後再依序把節點的字串記憶體空間釋放，節點本身釋放；最後再更動head即可。如果此節點為 queue 的最後一個節點，則把tail也指向NULL。

至此， queue 已經可以通過make test

剩下就是研究到底如何實現 command line system

qtest

qtest 裡面用到非常多static變數。但是static變數的生命週期能跨越檔案嗎？根據C99規格書 6.2.4.3 static

Its lifetime is the entire execution of the program and its stored value is initialized only once, prior to program startup.

原來是整個執行時期阿，那我就放心了。

do_new




















bool do_new(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    bool ok = true;
    if (q != NULL) {
        report(3, "Freeing old queue");
        ok = do_free(argc, argv);
    }
    error_check();
    if (exception_setup(true))
        q = q_new();
    exception_cancel();
    qcnt = 0;
    show_queue(3);
    return ok && !error_check();
}

report






















void report(int level, char *fmt, ...)
{
    va_list ap;
    if (!verbfile)
        init_files(stdout, stdout);
        //Output all the error message to the screen
    if (level <= verblevel) {
        va_start(ap, fmt);
        vfprintf(verbfile, fmt, ap);
        fprintf(verbfile, "\n");
        fflush(verbfile);
        va_end(ap);
        if (logfile) {
            va_start(ap, fmt);
            vfprintf(logfile, fmt, ap);
            fprintf(logfile, "\n");
            fflush(logfile);
            va_end(ap);
        }
    }
}

report 有一個很有趣的地方，參數輸入是...，也就是不定長度的傳入參數。關於這點C99在7.15有詳細的定義，先要用一個va_list來接住所有的參數，再來用va_start等來存取。如果有 logfile 則寫入。

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 trigger_exception(char *msg)
{
    error_occurred = true;
    error_message = msg;
    if (jmp_ready)
        siglongjmp(env, 1);
    else
        exit(1);
}

這兩個函數也是很有趣，一開始exception_setup被呼叫時，會先設定sigsetjmp的細節把諸如 stack pointer 儲存起來，之後如果trigger_exception被呼叫時，siglongjmp便會被呼叫進而進入exception_setup if 的上半部。
























/* 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);
}

接下來在利用 signal 系統呼叫來設定trigger_exception的條件，這樣便可以做到外部 exception handling 的功能。真是博大精深

do_remove_head

do_remove_head 比較複雜，以下分析將會利用註解來呈現（因為真的太長了阿阿阿）













































































bool do_remove_head(int argc, char *argv[])
{
    if (argc != 1 && argc != 2) {// 檢查參數個數是否合乎規定
        report(1, "%s needs 0-1 arguments", argv[0]);
        return false;
    }
    char *removes = malloc(string_length + STRINGPAD + 1);
    if (removes == NULL) { // 這裡移除用字串除了原本的 string_length 還多加了
        // padding 來檢查 memory leak
        report(1,
               "INTERNAL ERROR.  Could not allocate space for removed strings");
        return false;
    }
    char *checks = malloc(string_length + 1);
    if (checks == NULL) {// 檢查命令列所輸入的字串是否 malloc 成功
        report(1,
               "INTERNAL ERROR.  Could not allocate space for removed strings");
        free(removes);
        return false;
    }
    bool check = argc > 1;
    bool ok = true;
    if (check) {// 複製命令列所傳入之字串
        strncpy(checks, argv[1], string_length + 1);
        checks[string_length] = '\0';
    }

    removes[0] = '\0';//把 removes 第一個元素設為'\0'達到類似空字串的效果
    memset(removes + 1, 'X', string_length + STRINGPAD - 1);//把剩下的byte全部設成'X'
    removes[string_length + STRINGPAD] = '\0';//把最後一個byte設為'/0'
    //所以事實上 removes 有兩個 '\0'
    if (q == NULL) //做傳入 queue 檢查
        report(3, "Warning: Calling remove head on null queue");
    else if (q->head == NULL)
        report(3, "Warning: Calling remove head on empty queue");
    error_check();
    bool rval = false;
    if (exception_setup(true))// 開始上面的 outside exception handling
        rval = q_remove_head(q, removes, string_length + 1);
    exception_cancel();
    if (rval) {
        removes[string_length + STRINGPAD] = '\0';
        if (removes[0] == '\0') {//檢查是否有存到剛剛移除的字串
            report(1, "ERROR: Failed to store removed value");
            ok = false;
        } else if (removes[string_length + 1] != 'X') {
        // 檢查移除字串最後是否為'X'（應為'\0'），memory 是否有洩漏
            report(1,
                   "ERROR: copying of string in remove_head overflowed "
                   "destination buffer.");
            ok = false;
        } else {
            report(2, "Removed %s from queue", removes);
        }
        qcnt--;
    } else {// 如果剛剛的 rh 回傳失敗則執行以下
        fail_count++;
        if (!check && fail_count < fail_limit) {
            report(2, "Removal from queue failed");
        } else {
            report(1, "ERROR:  Removal from queue failed (%d failures total)",
                   fail_count);
            ok = false;
        }
    } 
    if (ok && check && strcmp(removes, checks) != 0) {
        // 比較移除字串和命令列所輸入字串是否相同。
        report(1, "ERROR:  Removed value %s != expected value %s", removes,
               checks);
        ok = false;
    }
    show_queue(3);
    free(removes);
    free(checks);
    return ok && !error_check();
}
Select a repo