2019q1 Homework1 (lab0)

contributed by < yunchi0921 >

tags: linux_kernel

---

題目需求

• 實作 queue.c
  • q_free : 釋放整個queue,包含其string
  • q_insert_tail : 在尾端插入元素
  • q_new : 新建一個queue
  • q_remove_head : 從開頭端刪除一個元素
  • q_reverse : 將queue反轉
  • q_size : 計算queue中元素數量

實作

queue_t

為了讓依題目要求q_size & q_insert_tail能再O(1)執行而新增一tail指標與qsize再插入與刪除時隨時紀錄。

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; /*In order to let q_insert_tail operate
                        in O(1)
                      */
    size_t qsize;
} queue_t;

q_free

因為要同時清除 string 與 list element 所以宣告*cur與*prev，每一次while迴圈中,prev指向cur位置,而cur指向下一個位址,由prev負責清除,直到cur指向NULL為止。

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

這裡藉由同學幫助發現當我q為NULL時，沒有返回return，則如果情況發生則會free到一個NULL的位置而產生問題。

修改如下

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

q_new

根據註解判斷queue是否為空,若不是則初始化各值並回傳。

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->qsize = 0;
    } else
        return NULL;

    return q;
}

q_insert_head

這裡值得注意的是tail的連接,實作方式是當queue的size為1時，就將tail指向新element。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (!q) {
        printf("quene is NULL\n");
        return false;
    } else {
        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) {
            // including null character
            newh->value = (char *) malloc(strlen(s) + 1);
            if(newh->value)
                strcpy(newh->value, s);
            newh->next = q->head;
            q->head = newh;
            (q->qsize)++;
            /*If only one element in queue ,
            head and tail are on same element.
            */
            if (q->qsize == 1)
                q->tail = newh;
            return true;
        } else {
            return false;
        }
    }
}

這邊也有一個問題，如果當newh->value配置失敗的時候，我應該free(newh)並return false，以避免memory leak。

修改如下，同時q_insert_tail也相同，不贅述直接修改程式碼。

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    if (!q) {
        printf("quene is NULL\n");
        return false;
    } else {
        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) {
            // including null character
            newh->value = (char *) malloc(strlen(s) + 1);
            if(newh->value)
                strcpy(newh->value, s);
            else{
                free(newh);
                return false;
            }
            newh->next = q->head;
            q->head = newh;
            (q->qsize)++;
            /*If only one element in queue ,
            head and tail are on same element.
            */
            if (q->qsize == 1)
                q->tail = newh;
            return true;
        } else {
            return false;
        }
    }
}

q_insert_tail

概念基本上跟q_insert_head差不多

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;
    /*If the q is NULL*/
    if (!q) {
        printf("queue is NULL\n");
        return false;
    } else {
        newh = malloc(sizeof(list_ele_t));
        if (newh) {
            newh->value = (char *) malloc(strlen(s) + 1);
            if(newh->value)
                strcpy(newh->value, s);
            else{
                free(newh);
                return false;
            }
            newh->next = NULL;
            if (q->tail != NULL)
                q->tail->next = newh;
            q->tail = newh;
            (q->qsize)++;
            /*If only one element in queue ,
              head and tail are on same element.
              */
            if (q->qsize == 1) {
                q->head = q->tail;
            }
            return true;
        } else {
            return false;
        }
    }
}

q_remove_head

根據註解sp不為NULL時要將刪除之 string 複製到sp中，且別忘記清除 string 以及 list element。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *prev = NULL;
    if (q->qsize != 0 && q != NULL) {
        if (sp != NULL) {
            memset(sp, '\0', bufsize);
            strncpy(sp, q->head->value, bufsize - 1);
        }
        prev = q->head;
        q->head = q->head->next;
        /*
          Free the element and the string
        */
        free(prev->value);
        free(prev);
        (q->qsize)--;
        return true;
    } else {
        return false;
    }
}

這邊有一個問題需要注意

if (q->qsize != 0 && q != NULL)

題目要求說，當queue為空以及q為NULL的時候回傳false，但因為我q->qsize寫在前面的關係，compiler在當q為NULL時，會判定我去讀一個NULL pointer，故應該要寫成以下型式

if (q!= NULL && q->size != 0)

q_size

題目要求在O(1)時間內執行，所以在queue.h更改queue_t新增qsize以達到此目的。

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 != NULL)
        return q->qsize;
    else
        return 0;
}

q_reverse

這邊我參考geeksforgeeks中3個指標的方式，裡頭有一個 gif 檔描述的相當清楚，但與我們不同的是，除了要改變 head ，同時也要改變 tail 。

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->qsize == 0)
        return;
    else {
        q->tail = q->head;
        list_ele_t *prev = NULL;
        list_ele_t *cur = q->head;
        list_ele_t *next = NULL;
        while (cur != NULL) {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        q->head = prev;
    }
}

testmalloc與testfree

感謝0xff07詳細的解釋

這邊主要對find_header 及find_free看看有什麼想講的，以及許多不懂的問題。

static block_ele_t *find_header(void *p)
{
    if (p == NULL) {
        report_event(MSG_ERROR, "Attempting to free null block");
        error_occurred = true;
    }
    block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t));
    if (cautious_mode) {
        /* Make sure this is really an allocated block */
        block_ele_t *ab = allocated;
        bool found = false;
        while (ab && !found) {
            found = ab == b;
            ab = ab->next;
        }
        if (!found) {
            report_event(MSG_ERROR,
                         "Attempted to free unallocated block.  Address = %p",
                         p);
            error_occurred = true;
        }
    }
    if (b->magic_header != MAGICHEADER) {
        report_event(
            MSG_ERROR,
            "Attempted to free unallocated or corrupted block.  Address = %p",
            p);
        error_occurred = true;
    }
    return b;
}

首先find_header主要是藉由block_ele_t的大小來推算出header在哪邊，接下來則是一連串的檢查機制。

block_ele_t *ab = allocated;
        bool found = false;
        while (ab && !found) {
            found = ab == b;
            ab = ab->next;
        }
        if (!found) {
            report_event(MSG_ERROR,
                         "Attempted to free unallocated block.  Address = %p",
                         p);
            error_occurred = true;
        }

這邊ab指向allocated這個doubly-linked list的開頭，並且在迴圈中搜尋這個block到底有沒有再這個串列裡頭

if (b->magic_header != MAGICHEADER) {
        report_event(
            MSG_ERROR,
            "Attempted to free unallocated or corrupted block.  Address = %p",
            p);
        error_occurred = true;
    }

這段程式我則不太明白，因為在test_malloc當中每個new_block的magic_header都會被指定成MAGICHEADER，這樣子與上一段的檢查，發現他已經是allocated的一個block，這樣子
b->magic_header一定會在test_malloc被指定為MAGICHEADER才對，有種重複檢查沒有必要感覺。

new_block->magic_header =MAGICHEADER;

我猜應該是因為 cautious mode 關閉的時候而存在的機制，不曉得正不正確。