Try   HackMD

2019q1 Homework1 (lab0)

contributed by <Zames-Chang>

認真看作業要求,除了提及如何逐步達到要求,還需要進行:

  1. 改善程式效能
  2. 解釋自動評分系統運作的原理
  3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標,請繼續付出!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

事前閱讀

基本上我們要完成這幾個function:

  • q new: 建立一個全新的 queue
  • q free: 把所有這個 queue所使用到的空間都 free掉
  • q insert head: 把元素放到 queue的最前面
  • q insert tail: 把元素放到 queue的最後面
  • q remove head: 刪除 queue的第一個元素
  • q size: queue有多長
  • q reverse: 把當前的 queue給反轉,但是不可以創建新的 queue去取代原本的 queue,要用當前的 queue去做

q_insert_tail and q_size 這兩個function必須要是

O(1) 不可以是
O(n)

實做

queue_t

/*
 為了滿足要是o(1),所以必須要在增加tail
 讓插入尾巴時不需要從頭路過到尾才能插入,
 且增加size屬性,每次insert or remove都紀錄size
 */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    size_t size;
} queue_t;

q_new

/*
 基本上就是 init queue_t的成員
 */
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (!q) {
        return NULL;
    }
    q->size = 0;
    q->head = NULL;
    q->tail = NULL;
    return q;
}

q_insert_head

/*
 size = strlen(s) + 1 因為有中止符號
 然後去 check malloc的過程中有沒有 null的發生,如果都沒有就是把 newh 裡面的資訊填一填,最後再把 q->head指向它就可以了。
 最後 size++去 maintain size的資訊
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    size_t size;
    if (!q)
        return false;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    if (!newh)
        return false;
    size = (size_t) strlen(s) + 1;
    newh->value = (char *) malloc(size);
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (!q->head) {
        newh->next = NULL;
        q->head = newh;
        q->tail = newh;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    q->size++;
    return true;
}

q_remove_head

/* 這一個 function是去把這個 element中所有的東西都 free掉不管是它本身有的指標還是指標指到的內容 且把文字給放入 sp這個暫存的 buffer中。 */ #define min(a, b) (((a) < (b)) ? (a) : (b)) bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { if (!q || !q->head) return false; list_ele_t *head = q->head; if (sp && head->value) { size_t len = min(strlen(head->value), bufsize - 1); memcpy(sp, head->value, len); sp[len] = '\0'; } q->head = q->head->next; free(head->value); free(head); q->size--; return true; }

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 *newh;
    size_t size;
    if (!q)
        return false;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    size = (size_t) strlen(s) + 1;
    newh->value = (char *) malloc(size);
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    newh->next = NULL;
    if (!q->head) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    q->size++;
    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) // 如果 q是指到 null 則回傳 0
        return 0;
    return q->size;
}

q_free

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t* remove_ele; //暫存準備要移掉的element
    if (q) {// 如果有 q存在
        if (!q->head){
            free(q); // 如果 q是空的
        }
        else{
            while(q->head){
                remove_ele = q->head;//先把要移掉的位址暫存起來
                q->head = q->head->next; //更新當前的頭指到的地方
                free(remove_ele->value); //把字串空間 free掉
                free(remove_ele); //把 element本身的空間 free掉
            }
            free(q);
        }
    }
}

改寫為下方程式碼: (減少縮排的深度和 scope)

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

    if (!q->head) {
        free(q);
        return;
    }

    while (q->head) {
        list_ele_t *remove_ele = q->head;
        q->head = q->head->next;
        free(remove_ele->value);
        free(remove_ele);
    }
    free(q);
}

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

2/26號更新

我之前為了測試環境提交了 commit,被罵惹,然後我用 git rebase試著想去刪掉那個 commit,可是不知道怎弄整個版本都壞掉了,我就整個砍掉重來 ORZ

幻滅是成長的開始,找出因應方法,繼續!

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

q_reverse

void q_reverse(queue_t *q) { if (q && q->head) { // check queue是否為空 list_ele_t *pre = q->head; list_ele_t *current = q->head->next; list_ele_t *next; list_ele_t *temp; while (current) { next = current->next; //把當前的下一個點存起來 current->next = pre; // 當前的元素只向上一個元素 pre = current; // 更新上一個元素 current = next; //更新當前元素 } q->head->next = NULL; // 把原本的 head指向終點 null //swap tail and head temp = q->head; q->head = q->tail; q->tail = temp; } /* You need to write the code for this function */ }

qtest 的行為

自動化評分時,會下 make test

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

所以看起來他是把 driver.py 餵給了 qtest,那我們先來看看 driver做了什麼

class Tracer: ... 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" } ...

從這段可以猜出他把 trace-01-15代到 qtest裡面跑,再去看
trace-01-ops.cmd

# Test of insert_head and remove_head
option fail 0
option malloc 0
new
ih gerbil
ih bear
ih dolphin
rh dolphin
rh bear
rh gerbil

所以大概就知道每一個 trace檔裡面放的都是 qtest的指令, driver的工作就是把每一個 trace檔都給 qtest跑過。
那來看看 他怎麼 check你有沒有 memory leak,發現他自己 maintain了一個變數叫allocated_count

size_t bcnt = allocation_check(); if (bcnt > 0) { report(1, "ERROR: Freed queue, but %lu blocks are still allocated", bcnt); size_t allocation_check() { return allocated_count; }

然後在哪裡這個變數會增加或減少呢?
這段程式碼取代了原本的malloc 跟free,也就是說每次我們做malloc跟free其實都是call下面兩個程式碼,在這兩段程式碼會有allocated_count++; and allocated_count--;,所以他檢查方式就是你allocate幾次空間,就應該要free掉幾次,如果你的最後次數相減不為零代表說你memory leak

... #define malloc test_malloc #define free test_free ... void *test_malloc(size_t size) { if (noallocate_mode) { report_event(MSG_FATAL, "Calls to malloc disallowed"); return NULL; } if (fail_allocation()) { report_event(MSG_WARN, "Malloc returning NULL"); return NULL; } block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t)); if (new_block == NULL) { report_event(MSG_FATAL, "Couldn't allocate any more memory"); error_occurred = true; } 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); new_block->next = allocated; new_block->prev = NULL; if (allocated) allocated->prev = new_block; allocated = new_block; allocated_count++; return p; } void test_free(void *p) { if (noallocate_mode) { report_event(MSG_FATAL, "Calls to free disallowed"); return; } if (p == NULL) { report(MSG_ERROR, "Attempt to free NULL"); error_occurred = true; return; } block_ele_t *b = find_header(p); size_t footer = *find_footer(b); if (footer != MAGICFOOTER) { report_event(MSG_ERROR, "Corruption detected in block with address %p when " "attempting to free it", p); error_occurred = true; } b->magic_header = MAGICFREE; *find_footer(b) = MAGICFREE; memset(p, FILLCHAR, b->payload_size); /* 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--; }

如何檢測 segmantation fault 跟時間超過呢

signal(SIGSEGV, sighandler) // if segmentation fault execute sighandler signal(SIGSLRM, sighandler) // if timeout execute sighandler