2019q1 Homework1 (lab0)

contributed by < ChienHisang >

tags: linux_kernel

---

作業目標 : 修改 queue.c 與 queue.h 並通過測試。

queue.h 功能說明:

• 定義 queue 結構
• 定義 node 結構
• 定義介面:
  • q_new()
  • q_free
  • q_insert_head
  • q_insert_tail
  • q_remove_head
  • q_size
  • q_reverse

queue.c 功能說明:

• 實作 queue.h 中定義的所有函數

---

修改 queue.h

原因 : 作業要求在 O(1) 內回傳該 queue 的長度與在 queue 尾部插入節點

struct queue_t

說明 : 加入 *tail 與 size。

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size; /*Linked list size*/
} queue_t;

修改 queue.c

原因 : 實作 queue.h 中所有函數

q_new()

說明 : 獲取一個 queue_t 大小的記憶體空間指派給q。

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()

說明 : cur 指向當前的 node，由於當前 node 會被 free 掉，所以在那之前需用 cur_next 暫存下一個 node 的地址，待當前 node 被 free 後再把下一個 node 的地址移交給 cur，反覆動作直到 cur==null，須注意當發現 queue 的 head 為 null 時，記得把queue free 掉。

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

    list_ele_t *cur = q->head, *cur_next = NULL;

    if (!cur) {
        free(q);
        return;
    }

    while (cur) {
        cur_next = cur->next;
        free(cur->value);
        free(cur);
        cur = cur_next;
    }

    free(q);
}

q_insert_head()

說明 : 將新增的 node 加在當前 queue 的最前端，需特別注意當前 queue 的 node 數，若新增的 node 為該 queue 中的第一個節點，則不需作將原本的 head 指派給 node->next。

bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newh;

    newh = malloc(sizeof(list_ele_t));

    if (!newh)
        return false;

    newh->value = malloc(sizeof(char) + strlen(s));

    if (!newh->value) {
        free(newh);
        return false;
    }

    strcpy(newh->value, s);
    newh->next = NULL;

    if (!q->head)
        q->head = newh;
    else {
        newh->next = q->head;
        q->head = newh;
    }

    if (!q->tail)
        q->tail = newh;

    q->size++;

    return true;
}

q_insert_tail()

說明 : 因為在 queue_t 中加入 tail 指標，故能在 o(1) 內將新增的 node 插入 queue 結尾，須注意 malloc 給 node->value 時，記得幫 char 陣列結尾符號'\0'留位子，可以是 1 或 sizeof(char)，還須注意當前 queue 中的 node 數。

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q)
        return false;

    list_ele_t *newt = malloc(sizeof(list_ele_t));

    if (!newt)
        return false;

    newt->value = malloc(sizeof(char) + strlen(s));

    if (newt->value) {
        strcpy(newt->value, s);
        newt->next = NULL;
    } else {
        free(newt);
        return false;
    }

    if (q->tail)
        q->tail->next = newt;

    q->tail = newt;

    if (!q->head)
        q->head = newt;

    q->size++;

    return true;
}

q_remove_head()

說明 : 將head值移轉給sp後，把head指標只給原本head的next node，須注意memeset的使用方法。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !sp || !q->head || !q->head->value)
        return false;

    list_ele_t *tmp = q->head;

    memset(sp, '\0', bufsize);
    strncpy(sp, tmp->value, bufsize - 1);
    q->head = tmp->next;

    if (!q->head)
        q->tail = NULL;

    free(tmp->value);
    free(tmp);
    q->size--;

    return true;
}

q_size()

說明 : 在O(1)時間內返回值，故無法使用遍例queue的方式，因此在queue_t中加入size，因為size不可能為負值，故宣告成size_t 或 unsigned int會更好。

int q_size(queue_t *q)
{
    if (!q || !q->head)
        return 0;

    return q->size;
}

q_reverse()

說明 : 將cur指到的node的next指給pre指向的node，由於這個動作或造成cur指到的node之next丟失，所以在這之前需要用next_tmp將其保存下來，完成動作後，pre向後一格，cur也向後一格，反覆直到cur為null，最後記得把queue中的head與tail對調。

void q_reverse(queue_t *q)
{
    if (!q || !q->head || !q->head->next)
        return;

    list_ele_t *pre = q->head, *cur = q->head->next, *next_tmp = NULL;

    pre->next = NULL;

    while (cur) {
        next_tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next_tmp;
    }

    q->tail = q->head;
    q->head = pre;
}