2019q1 Homework1 (lab0)

contributed by < guojiun >

實作流程

q new:

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

q free:

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

q insert head:

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (q == NULL) 
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;

    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
        newh->next = NULL;
    } else {
        newh->next = q->head;
        q->head = newh;
    }
    (q->size)++;
    return true;
}

其中，第 20 行與第 25 行相同，可移出來，改寫後如下：

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

此外，當 q->head == NULL 時 newh->next = NULL;，不就是 new->next = q;，這又和第5 行相同，所以可以移出來 :

if (q->head == NULL) {
    q->tail = newh;
} 
newh->next = q->head;
q->head = newh;

q insert tail:

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 */
    if (q == NULL) 
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }
    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strcpy(newh->value, s);
    newh->next = NULL;
    if (q->head == NULL) {
        q->head = newh;
        q->tail = newh;
    } else {
        q->tail->next = newh;
        q->tail = newh;
    }
    (q->size)++;
    return true;
}

其中，第 21 行與第 24 行相同，可移出來。改寫後如下：

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

其實，q->head = newh 是可省略的，換言之，上述又可改寫為：

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

q remove head:

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->size == 0)
        return false;
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize-1);
        sp[bufsize - 1] = '\0';
    }
    free(q->head->value);
    list_ele_t *newh = q->head->next;
    free(q->head);
    q->head = newh;
    (q->size)--;
    return true;
}

q size:

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 0;
    return q->size;
}

q reverse:

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

cppcheck -> false alarm
AddressSanitizer (ASAN)

自動測試程式運作機制

1. 測試
2. 記憶體使用追蹤機制
3. Segmentattion fault 的檢測
4. 超時

程式什麼時候會 shutdown ?