2019q1 Homework1 (lab0)

contributed by < fakepaper56 >

初步實作

queue_t

typedef struct {
    list_ele_t *head; /* Linked list head of elements */
    list_ele_t *tail; /* Linked list tail of elements */
    int size;         /* the number of linked list elements */    
} queue_t;

因為我們希望可以用 O(1) 的時間複雜度實踐FIFO與數量查詢，所以我就在queue_t裡增加了tail與size.

q_new

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

這邊我覺得值得探究，如果這個專案可以使用 calloc()的話，是否用calloc()比較划算？

q_free

void q_free(queue_t *q)
{
    if (q) {
        while (q->head) {
            list_ele_t *tmp = q->head;
            q->head = tmp->next;
            free(tmp->value);
            free(tmp);
        }
        /* Free queue structure */
        free(q);
    }
}

這邊比較值得講的是free()的先後順序，必須先把子結構free()掉再free()掉母結構。

q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;

    /* Return false if q is NULL or could not allocate space */
    if (!q || (newh = malloc(sizeof(list_ele_t))) == NULL)
        return false;

    /* Allocate space for the string and copy it */
    if ((newh->value = strdup(s)) == NULL) {
        free(newh);
        return false;
    }

    if (!q->head) { /* q is empty */
        /* Hence the tail is the new head */
        q->tail = newh;
    }
    newh->next = q->head;

    /* Update the new head */
    q->head = newh;
    /* Update the new size */
    ++q->size;
    return true;
}

q_insert_head

bool q_insert_tail(queue_t *q, char *s)
{
    list_ele_t *newt;

    /* Return false if q is NULL or could not allocate space */
    if (!q || (newt = malloc(sizeof(list_ele_t))) == NULL)
        return false;

    /* Allocate space for the string and copy it */
    if ((newt->value = strdup(s)) == NULL) {
        free(newt);
        return false;
    }

    newt->next = NULL;

    if (!q->head) {
        /* Hence the head is the new tail */
        q->head = newt;
    } else {
        q->tail->next = newt;
    }

    /* Update the new tail */
    q->tail = newt;
    /* Undate the new size */
    ++q->size;
    return true;
}

這兩個函數比較要注意的是，在要幫新的節點malloc()字串部份失敗的時候，要記得把節點free()掉再離開函數。

q_remove_head

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

    if (!sp)
        return false;

    list_ele_t *head = q->head;
    strncpy(sp, head->value, bufsize - 1);
    sp[bufsize - 1] = '\0';

    /* update the new head.*/
    q->head = head->next;

    /* free the orign head.*/
    free(head->value);
    free(head);

    --q->size;
    return true;
}

這個函數是我寫這個作業搞最久的一個問題。問題是出在我以為strncpy()使用完之後，他會像strcpy()一樣把最後一格填上'\0'。但strncpy(3)卻這樣說：

Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.

追根究底會花這麼多的時間在這題，我覺得除了對C語言規格不夠熟悉外，也需要對像GDB這樣的工具多點了解。

q_size

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

q_reverse

void q_reverse(queue_t *q)
{
    /* we only need to deal with the queue having more than 2 elements */
    if (!q || q->size < 2)
        return;

    /* reverse the list */
    q->tail = q->head;

    list_ele_t *tmp, *fast = q->head->next;

    while (fast) {
        tmp = q->head;
        q->head = fast;
        fast = fast->next;
        q->head->next = tmp;
    }
    q->tail->next = NULL;
}