2019q1 Homework1 (lab0)

contibuted by < W >

請注意看作業要求，填入 GitHub 帳號名稱

jserv

開發環境

​Architecture:        x86_64
CPU op-mode(s):      32-bit, 64-bit
Byte Order:          Little Endian
CPU(s):              8
On-line CPU(s) list: 0-7
Thread(s) per core:  2
Core(s) per socket:  4
Socket(s):           1
NUMA node(s):        1
Vendor ID:           GenuineIntel
CPU family:          6
Model:               94
Model name:          Intel(R) Core(TM) i7-6700HQ CPU @ 2.60GHz
Stepping:            3
CPU MHz:             1015.293
CPU max MHz:         3500.0000
CPU min MHz:         800.0000
BogoMIPS:            5184.00
Virtualization:      VT-x
L1d cache:           32K
L1i cache:           32K
L2 cache:            256K
L3 cache:            6144K
NUMA node0 CPU(s):   0-7

queue.h

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
                      */
    list_ele_t *tail;
    int size;
} queue_t;

在struct裡 tail 和 size ，使一些function可以在O(1)裡完成

queue.c

q_new()

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

如果malloc成功就把新產生的 queue_t 初始化

q_free()

void q_free(queue_t *q)
{
    if (!q)
        return;
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    list_ele_t *ele = NULL, *ele_tmp = NULL;
    for (ele = q->head; ele != NULL; ele = ele_tmp) {
        free(ele->value);
        ele_tmp = ele->next;
        free(ele);
    }
    free(q);
}

從head開始依序將每個node的value及整個node free

q_insert_head()

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    newh->value[strlen(s)] = '\0';
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;
    return true;
}

只要有一個malloc不成功就要將整個新產生的node跟裡面的value要求的空間free掉
若malloc都成功，先將s字串複製一份到value，並再字串尾加上 '\0'
然後將 next 指向 head 指的node，接著把自己丟給 head
若此node是第一個產生的node，也把自己丟給 tail
將 size +1

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 */
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc((strlen(s) + 1) * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    newh->value[strlen(s)] = '\0';
    newh->next = NULL;
    if (q->tail != NULL)
        q->tail->next = newh;
    q->tail = newh;
    if (q->size == 0)
        q->head = newh;
    q->size++;
    return true;
}

只要有一個malloc不成功就要將整個新產生的node跟裡面的value要求的空間free掉
若malloc都成功，先將s字串複製一份到value，並再字串尾加上 '\0'
然後將 next 指向 NULL
接著 判斷一下tail是否有node，若不判斷直接寫 q->tail->next 會產生錯誤
( 因為若是 q->tail 指向 NULL 就沒能指向 next 指標 )
接著把自己丟給 tail
若此node是第一個產生的node，也把自己丟給 head
將 size +1

(p.s.) 因為在.h檔新增的tail，使此function可以實現在O(1)裡完成
要是沒有紀錄tail，此function為了找到最尾端，勢必要將整個list從頭找到尾，此時需要O(n)

q_remove_head()

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;
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_ele_t *ele_tmp = NULL;
    ele_tmp = q->head;
    q->head = q->head->next;
    free(ele_tmp->value);
    free(ele_tmp);
    q->size--;
    return true;
}

首先若q指向NULL或目前沒有任何node => 此指令不能運作
接著若是sp指向non_NULL就將要刪除的node的value依據bufsize的長度限制複製進去
但若是sp指向NULL則不用複製
接著用一個 ele_tmp 先把head指向的地方複製一份放著
並將head指向目前指向的node的next
接著運用ele_tmp將原先指向的node的value和整個node清掉
將 size -1

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

回傳目前有幾個node
因為在.h檔新增的size使我們每經過一步操作都可以隨時掌握node的數量
此時可以實現在O(1)回傳node的數量

q_reverse()

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

說明待補，需要圖片輔助

遇到的問題

此次作業除了上述問題，其實還有一個更根本的問題，從github clone下來的初始檔案並非正常的，運用指令 ＄cppcheck *.[ch] （此指令的意思是對所有.c .h檔做cppcheck）

Checking console.c ...
1/9 files checked 26% done
Checking console.h ...
2/9 files checked 30% done
Checking harness.c ...
[harness.c:147]: (error) Address of auto-variable 'new_block->payload' returned
3/9 files checked 41% done
Checking harness.h ...
Checking harness.h: INTERNAL...
4/9 files checked 43% done
Checking qtest.c ...
5/9 files checked 69% done
Checking queue.c ...
Checking queue.c: INTERNAL...
6/9 files checked 76% done
Checking queue.h ...
7/9 files checked 80% done
Checking report.c ...
8/9 files checked 95% done
Checking report.h ...
9/9 files checked 100% done

我們可以發現在harness.c的第147行會發生錯誤

147 return p;

再看看我們的錯誤指令 Address of auto-variable 'new_block->payload' returned
上網查了一下 auto-variable 是局部變數/區域變數的意思
我們再往上找

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

再往上找 payload

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

發現他是一個 unsigned char[0]
待補