# 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)](https://linux.die.net/man/3/strncpy)卻這樣說：
> 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;
}