2019q1 Homework1 (lab0)

contributed by <Zames-Chang>

• C Programming Lab
• F01: lab0

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

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

還未達成符合預期目標，請繼續付出！

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

jserv

2/26號更新

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

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

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