2020q3 Homework1 (lab0)

contributed by < chewei3 >

Outline

作業要求

在 queue.[ch] 中完成以下實作

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 以遞增順序來排序鏈結串列的元素

實作

queue.h

• 修改 queue_t ，加入 list_ele_t *tail 及 int size 使得q_size以及 q_insert_tail 能夠在
  $O(1)$ 時間完成
• 加入 list_ele_t *tail 的缺點是使用的記憶體空間增加， queue operation 需要維護 q->tail

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

queue.c

q_new

建立新的 queue ，需考慮 malloc 失敗的情況

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

q_free

釋放 queue 的所有記憶體，需檢查

• queue是否為NULL
• free value
• free node

void q_free(queue_t *q)
{
    if (!q) return;
    list_ele_t *head = q->head;
    while (head) {
        q->head = head->next;
        free(head->value) ;
        free(head);
        head = q->head;
    }
    free(q);
}

q_insert_head

插入新的 node 到 queue 的 head ，需考慮

• node malloc 失敗直接return
• node->value malloc失敗需要 free node
• 若 queue 為空，要 assign q->tail list_ele_t *newh

因為用 strcpy 將 char *s copy 到 node->value 會報錯，所以參考 qtest.c 使用 strncpy

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q) return false;
    /* TODO: What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    size_t len = strlen(s) + 1;
    newh->value = (char *)malloc( len * sizeof(char));
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len);
    /* 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)
        q->tail = newh;
    q->size++;
    return true;
}

q_insert_tail

因為有額外記住 q->tail，所以可以用

$O(1)$ 時間插入
作法跟 q_insert head 類似

bool q_insert_tail(queue_t *q, char *s)
{

    if (!q) return false;
    /* TODO: What should you do if the q is NULL? */
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    size_t len = strlen(s) + 1;
    newh->value = (char *)malloc( len * sizeof(char));
    newh->next = NULL;
    if (!newh->value) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len);
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */

    if (!q->size)
        q->head = newh;
    else
        q->tail->next = newh;
    q->tail = newh;
    q->size++;
    
    return true;
}

q_remove_head

• 若 char *sp 非空，需要 assign head->value 給它

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;
    list_ele_t *head = q->head;
    q->head = q->head->next;
    q->size--;
    if (head->value) {
        if (sp) {
            size_t len = bufsize > strlen(head->value) ? strlen(head->value) : bufsize - 1;
            strncpy(sp, head->value, len);
            sp[len] = '\0';
        }
        free(head->value);
    }

    free(head);
    return true;
}

q_size

int q_size(queue_t *q)
{
    return q ? q->size : 0;
}

q_reverse

跟 quiz1 的作法相同，需額外維護 q->tail

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

    list_ele_t *cursor = NULL;
    q->tail = q->head;
    while (q->head) {
        list_ele_t *next = q->head->next;
        q->head->next = cursor;
        cursor = q->head;
        q->head = next;
    }
    q->head = cursor;
}

q_sort

參考 作業說明連結 使用MergeSort，後來有看到 Zhumon 的 merge可以將 merge 及 merge_sort合併

• TODO: 合併 merge 及 merge_sort

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    list_ele_t *tmp = NULL;
    if (strcmp(l1->value, l2->value) <= 0) {
        tmp = l1;
        l1 = l1->next;
    } else {
        tmp = l2;
        l2 = l2->next;
    }

    list_ele_t *head = tmp;
    while (l1 && l2) {
        if (strcmp(l1->value, l2->value) <= 0) {
            tmp->next = l1;
            tmp = tmp->next;
            l1 = l1->next;
        } else {
            tmp->next = l2;
            tmp = tmp->next;
            l2 = l2->next;
        }
    }

    if (l1) tmp->next = l1;
    if (l2) tmp->next = l2;

    return head;
}

void merge_sort(list_ele_t **head)
{
    if (!*head || !(*head)->next)
        return;
    list_ele_t *fast = (*head)->next;
    list_ele_t *slow = *head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;

    merge_sort(head);
    merge_sort(&fast);
    *head = merge(*head, fast);
}

Valgrind

待補
還沒有看這部分，目前只有把結果跑出來

trace-17-complexity 結果

Perf

因為 trace-17 有時候不會通過，用 Perf 去看效能瓶頸在哪

結果發現 q_insert_head 佔據了 15.7% 的執行時間，但是在 trace-17 裡面並沒有 insert_head
待補