2018q3 Homework2 (lab0)

typedef struct {
    list_ele_t *head; /* Linked list of elements */
                      /*
                        You will need to add more fields to this structure
                        to efficiently implement q_size and q_insert_tail
                      */
    list_ele_t *q_tail;
    int q_size;
} queue_t;

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)  // Return NULL if could not allocate space
        return NULL;
    q->head = NULL;

    q->q_tail = NULL;
    q->q_size = 0;

    return q;
}

void q_free(queue_t *q)
{
    if (q == NULL)
        return;

    while (q->head) {
        list_ele_t *tmp = (q->head);
        q->head = (q->head)->next;
        free(tmp);
    }
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    free(q);
}

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)  // Return false if q is NULL
        return false;

    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)  // could not allocate space
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->next = q->head;

    newh->value = strdup(s);
    if (q->q_size == 0) {
        q->q_tail = newh;
    }

    q->head = newh;
    (q->q_size)++;

    return true;
}

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 if q is NULL
        return false;

    list_ele_t *new;
    new = malloc(sizeof(list_ele_t));
    if (new == NULL)  //  could not allocate space
        return false;

    new->next = NULL;
    new->value = strdup(s);
    if (q->q_size == 0) {
        q->head = new;
    } else {
        q->q_tail->next = new;
    }

    q->q_tail = new;
    q->q_size++;

    return true;
}

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if ((q == NULL) ||
        (q->q_size == 0))  // Return false if queue is NULL or empty.
        return false;

    if (sp) {  // If sp is non-NULL
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        int string_size = strlen(tmp->value);
        string_size =
            (string_size > (bufsize - 1))
                ? (bufsize - 1)
                : string_size;  // up to a maximum of bufsize-1 characters
        strncpy(sp, tmp->value, string_size);  // copy the removed string to *sp
        sp[string_size] = '\0';                // plus a null terminator
        free(tmp);
        q->q_size--;
        return true;
    }

    return false;
}

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 if q is NULL
        return 0;
    return q->q_size;
}

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if ((q == NULL) || (q->q_size == 0))  // No effect if q is NULL or empty
        return;

    list_ele_t *next_element;
    list_ele_t *current = q->head;
    list_ele_t *previous = NULL;

    q->q_tail = q->head;

    while (current) {
        next_element = current->next;
        current->next = previous;
        previous = current;
        current = next_element;
        q->head = previous;
    }
}

TOTAL		7/100

TOTAL		48/100

TOTAL		81/100

TOTAL	    100/100

fs@fs-ubuntu:~/lab0-c$ cat /etc/os-release 
NAME="Ubuntu"
VERSION="16.04.3 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.3 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial
fs@fs-ubuntu:~/lab0-c$ cat /proc/version
Linux version 4.10.0-28-generic (buildd@lgw01-12) (gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4) ) #32~16.04.2-Ubuntu SMP Thu Jul 20 10:19:48 UTC 2017

test: qtest scripts/driver.py
	scripts/driver.py