2019q1 Homework1 (lab0)

contributed by < wang0630 >

認真看作業要求，除了提及如何逐步達到要求，還需要進行:

1. 改善程式效能
2. 解釋自動評分系統運作的原理
3. 提及 qtest 的行為和裡頭的技巧

還未達成符合預期目標，請繼續付出！

jserv

Goal

According to the pdf file, we need to implement the following core operations of queue:

1. Create a queue
2. Free all spaces allocated for the queue
3. Insert a new node at the head of the queue
4. Insert a new node at the tail of the queue
5. Pop out the node at the head of the queue
6. Return the number of nodes in the queue

Implementation

1. Create a new queue:

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        fprintf(stderr, "Malloc call returns null");
    else { 
        q->head = q->tail = NULL;
        q->qsize = 0;
    }
    return q;
}

2. Free all spaces allocated for the queue:

void q_free(queue_t *q)
{
    if (!q)
        return;
    list_ele_t *prev = NULL;
    if (q->qsize) {
        for (list_ele_t *iter = q->head; iter;) {
            free(iter->value);
            prev = iter;
            iter = iter->next;
            free(prev);
        }
    }
    free(q);
}

3. Insert a new node at the head of the queue:

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(strlen(s) + 1);
    if (!newh->value) {
        free(newh);  // free the new node since it is allocated spaces
        return false;
    }
    memset(newh->value, 0, strlen(s) + 1);
    if (s)
        strcpy(newh->value, s);
    newh->next = q->head;  // new node's next to first element or to null if the
                           // queue is empty
    q->head = newh;        // insert new node
    // if queue is empty before insertion, q->tail should be pointed to the newh
    // as well
    q->tail = !q->qsize ? newh : q->tail;
    q->qsize++;
    return true;
}

4. Insert a new node at the tail of the queue:

bool q_insert_tail(queue_t *q, char *s)
{
    // maintain a tail field in the queue_t structure to achieve O(1) insertion
    if (!q)
        return false;
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    newh->value = malloc(strlen(s) + 1);
    if (!newh->value) {
        free(newh);
        return false;
    }
    memset(newh->value, 0, strlen(s) + 1);
    if (s)
        strcpy(newh->value, s);
    newh->next = NULL;  // tail node's next must be null
    if (q->qsize)
        q->tail->next = newh;
    q->tail = newh;
    // if queue is empty before insertion, q->head should be pointed to the newh
    // as well
    q->head = q->qsize ? q->head : newh;
    q->qsize++;
    return true;
}

5. Pop out the node at the head of the queue:

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->qsize)
        return false;
    if (sp) {                    // if sp is non-NULL
        memset(sp, 0, bufsize);  // clear sp to safely contain the string
        strncpy(sp, q->head->value, bufsize - 1);
    }
    list_ele_t *tmp = q->head;  // hold the target node
    q->head = q->head->next;    // remove the head
    q->qsize--;
    // if queue is empty after the removal, q->tail should be null as well
    q->tail = q->qsize ? q->tail : NULL;
    // free the target node
    free(tmp->value);
    free(tmp);
    return true;
}

6. Return the number of nodes in the queue:

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

7. Reverse the queue:

void q_reverse(queue_t *q)
{
    if (!q || !q->qsize || q->qsize == 1)
        return;
    list_ele_t *prev, *cur, *nextele;
    prev = q->head;
    cur = nextele = q->head->next; // q->head->next must exist, there is at least two nodes
    while (cur) {
        nextele = nextele->next;
        cur->next = prev;
        prev = cur;  // move prev
        cur = nextele;
    }
    list_ele_t *tmpHead = q->head;
    q->head->next = NULL;
    q->head = q->tail;
    q->tail = tmpHead;
}

Tools I learned in this assignment:

1. valgrind:
   A analysis tool to discover the partial errors.
   Useful flags:

• --track-fds: track open file fds
• --leak-check: track partial memory leak