2018q3 Homework2 (lab0)

contributed by <ian910297>

記得補上實驗環境
課程助教

已補上
ian910297

實驗環境
























Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                1
On-line CPU(s) list:   0
Thread(s) per core:    1
Core(s) per socket:    1
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 62
Model name:            Intel(R) Xeon(R) CPU @ 2.50GHz
Stepping:              4
CPU MHz:               2500.000
BogoMIPS:              5000.00
Hypervisor vendor:     KVM
Virtualization type:   full
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              30720K
NUMA node0 CPU(s):     0
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid pni pclmulqdq ssse3 cx16 pcid sse4_1 sse4_2 x2apic popcnt aes xsave avx f16c rdrand hypervisor lahf_lm pti fsgsbase tsc_adjust smep erms xsaveopt arch_capabilities

在開始寫作業之前，馬上遇到一個問題『要如何去跟原本的專案 fetch 新的資料到我自己 fork 的專案』

參考【狀況題】怎麼跟上當初 fork 專案的進度？

# 新增原來專案的位置
git remote add hw2 https://github.com/sysprog21/lab0-c

# 至遠端取資料
git fetch hw2

# 將 fetch 到的資料與原本的 master 做 merge
git merge hw2/master

# 自行決定是否要 push 到 fork 的專案，因為本機端已經是最新的版本了
git push

之後需要再更新時就可以使用：
1.$git stash 暫存現在自己的開發進度
2.$git pull hw2 [branch] 拉原本專案的新信度
3.$git stash pop 解決 conflict

課程助教

這次作業的要求只需要修改 queue.h, queue.c 這兩個檔案

先看到 queue.h 的部份，從提示裡面可以發現，要針對 q_size() 跟 q_insert_tail() 這兩個 function ，特別去做設計

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;// for q_insert_tail
    int size;// for q_size
} queue_t;

讓我們一個一個測試來看，總共有 14 個測試需要完成，目前只有實作到 72/100 的部份，會先補上實作的程式碼

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->size = 0;
    return q;
}

q_free() 部分只是依序檢查 list_ele_t 以及 value 是否為 NULL ，並將其佔用的記憶體給釋放

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if(!q) {
        return;
    }

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

    free(q);
}

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


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

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

    if(q->size == 0) {
        q->head = q->tail = newh;
        q->size += 1;
        return true;
    }

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

    return true;
}

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 */
    if(!q) {
        return false;
    }

    list_ele_t *newt;
    newt = malloc(sizeof(list_ele_t));
    if(!newt) {
        return false;
    }

    newt->value = malloc(sizeof(char) * strlen(s) + 1);
    if(!newt->value) {
        free(newt);
        return false;
    }
    strcpy(newt->value, s);

    newt->next = NULL;
    if(q->size == 0) {
        q->head = q->tail = newt;
        q->size += 1;
        return true;
    }

    q->tail->next = newt;
    q->tail = newt;
    q->size += 1;

    return true;
}

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{   
    /* You need to fix up this code. */
    if(!q || q->size == 0) {
        return false;
    }
    
    list_ele_t *tmp = q->head;
    
    if(q->size > 1) {
        q->head = q->head->next;
    } else {
        q->head = NULL;
    }
    
    if(!sp) {
        if(tmp->value) {
            free(tmp->value);
        }
        
        free(tmp); 
        q->size -= 1;
        
        return true;
    }
    
    int valuesize = strlen(tmp->value);
    //int spsize = strlen(sp);
    
    if(bufsize < valuesize) {// insert bufsize
        memset(sp, '\0', sizeof(char) * bufsize);
        memcpy(sp, tmp->value, sizeof(char) * bufsize - 1);
    } else {// insert valuesize
        memset(sp, '\0', sizeof(char) * valuesize + 1);
        memcpy(sp, tmp->value, sizeof(char) * valuesize);
    }
    
    free(tmp->value);
    free(tmp); 
    q->size -= 1;
    
    return true;
}

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->size==0) {
        return 0;
    }

    return q->size;
}

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if(!q || !q->head || q->size==0) {
        return;
    }

    // find the element before tail
    list_ele_t *cur, *oldtail, *next, *prev;
    cur = q->head;
    oldtail = q->tail;
    q->tail = q->head;

    next = cur->next;
    while(next != oldtail) {
        prev = cur;
        cur = next;
        next = cur->next;
        cur->next = prev;
    }

    next->next = cur;
    q->tail->next = NULL;
    q->head = oldtail;
}