2019q3 Homework2 (lab0)

contributed by < tommywang0tw >

tags: 王志瑋

Homework Requirement

reference: C programming Lab

Task

1. Modify the code in queue.h and queue.c to fully implement the following functions:
   • q_new: Create a new, empty queue.
   • q_free: Free all sorage used by a queue.
   • q_insert_head: Attempt to insert a new element at the head of the queue (LIFO discipline).
   • q_insert_tail: Attempt to insert a new element at the tail of the queue (FIFO discipline).
   • q_remove_head: Attempt to remove the element at the head of the queue.
   • q_size: Compute the number of elements in the queue.
   • q_reverse: Recorder the list so that the queue elements are reversed in order (It should rearrange the existing elements).
2. Test
   • Compile the code using this command: linux> make
   • Implement the executable file which is generated by the compiler by using linux> ./qtest
   • Test the effect of the code and debug
   • Evaluate the program by using linux> make test
   • Try to get the perfect score

Skills Tested:

• Explicit memory management, as required in C.
• Creating and manipulating pointer-based data structures.
• Working with strings.
• Enhancing the performance of key operations by storing redundant information in data structures.
• Implementing robust code that operates correctly with invalid arguments, including NULL pointers.

Functions Implementation

Queue structure

In order to efficiently implement q_size and q_insert_tail, we add a pointer called tail to point the end of the queue and a integer called size to record the size of this queue.

Code:

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 *tail;
    int size;
} queue_t;

q_new

Expected functionality

• Set the initial condition
• Allocate space for this queue structure, and it should be able to handle malloc failure

Code

We allocate space for this queue structure and make the head pointer point to NULL. If the malloc fails, the pointer q would be assigned NULL. We use this attribute to detect malloc failure.

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q == NULL)
    {
      printf("can't allocate space for the queue.\n");
      return NULL;
    }
    q->head = NULL;
    return q;
}

q_free

Expected functionality

• Handle if the input queue doesn't exist
• Free all storage used by queue, including the queue structure, every elements, and those strings pointed by each element

Code

In this code, we use two pointer(temp, prev) to go through this queue. Prev points to the element temp just went through. Everytime when temp goes through a element, we free the string that element points to. After that, prev will go through this element and free it.

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /*Do nothing if the queue doesn't exist*/
    if (q == NULL) {
        return;
    }
    /*Use pointer temp to go through the whole
     queue and free the strings*/
    /*Use prev pointer to access the elements which 
    temp just deleted their value, then we free the element*/
    list_ele_t *prev = q->head;
    list_ele_t *temp = q->head;
    while (temp != NULL) {
        free(temp->value);
        prev = temp;
        temp = temp->next;
        free(prev);
    }
    free(q);
}

q_insert_head

Expected Functionality

• Allocate space for the element and the string which is going to be pointed by that element
• copy the input string to the allocated space
• Handle queue non-existing situation
• Handle empty queue situation
• Handle malloc failure

Code

First, we handle the special conditions like: queue doesn't exist(q == NULL), malloc failure when allocating space for string or element. Note that, at line 29, we need to free the space we just allocated or it would be memory leak.
Then we need to do the right move corresponding two situations: queue is empty or not. If it is, we need to point both the head and tail pointer to this new element. Also, the new element should point to NULL. If it's not, we make the new element point to the old head element, then point the head point to the new element. (after line 35)

bool q_insert_head(queue_t *q, char *s)
{
    /*Handle q not-existing situation*/
    if (q == NULL) {
        printf("This queue doesn't exist!\n");
        return false;
    }
    list_ele_t *newh;
    int str_size;
    char *copy_s;
    /* If q is NULL, we new a queue and then
    insert the element to the head of this queue*/

    /*Allocate space for the string*/
    str_size = strlen(s) + 1;
    copy_s = malloc(str_size * sizeof(char));
    /*Handle malloc failure*/
    if (copy_s == NULL) {
        printf("Couldn't allocate space for the string!\n");
        return false;
    }
    /*Allocate space for the element*/
    newh = malloc(sizeof(list_ele_t));
    /*Handle malloc failure*/
    if (newh == NULL) {
        printf("Couldn't allocate space for the element!\n");
        /*If this function fails here, we need to
        free the space we allocated above*/
        free(copy_s);
        return false;
    }
    strcpy(copy_s, s);

    newh->value = copy_s;
    /*Handle empty queue situation*/
    if (q->head == NULL) {
        q->tail = newh;
        newh->next = NULL;
    } else /*General situation*/
    {
        newh->next = q->head;
    }
    q->head = newh;

    /*Count size of queue*/
    q->size++;
    return true;
}

q_insert_tail

q_insert_tail is highly similar to q_insert_head, the functionality is the same and also the special conditions and situations need to be handled. In order to keep this note short, I won't elaborate this function here because the content would be almost the same.

Note: we are required to implement this function in O(1). The key point to do so is in the queue structure declaration. We declared the tail pointer in this structure so that we can easily use the same method as q_insert_head and implement this function in constant time.

Code

bool q_insert_tail(queue_t *q, char *s)
{
    /*Handle queue not-existing situation*/
    if (q == NULL) {
        printf("This queue doesn't exist!\n");
        return false;
    }
    list_ele_t *newt;
    char *copy_s;
    int str_size;
    str_size = strlen(s) + 1;

    /*Allocate space for the new element and the string will be pointed to*/
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        printf("Couldn't allocate space for the element!\n");
        return false;
    }
    copy_s = malloc(str_size * sizeof(char));
    if (copy_s == NULL) {
        printf("Couldn't allocate space for the string!\n");
        /*If the function fails here, we need to free the space we allocate
        above to avoid memory leaking*/
        free(newt);
        return false;
    }
    strcpy(copy_s, s);
    newt->value = copy_s;
    newt->next = NULL;
    /*Handle empty queue situation*/
    if (q->head == NULL) {
        q->head = newt;
        q->tail = newt;
        q->size++;
        return true;
    }
    q->tail->next = newt;
    q->tail = newt;
    q->size++;
    return true;
}

q_remove_head

Expected Functionality

• Attempt to remove the element from head of queue, return true if successful, false if queue is NULL or empty
• If the passed pointer sp is non-NULL and the remove is implemented successfully, copy the removed string to it
• Free the space used by the removed element and string

Code

First, we use a simple if statement to handle the situations that q is empty or doesn't even exist(q==NULL or q->head==NULL). Then we check if sp is non-NULL. If it is, we need to copy the string we are about to remove to sp.
(Note: we need to put the terminator at the end of string in sp manually because if the size of the removed string is equal or larger than bufsize-1, strncpy won't copy the terminator to sp.)
Then, we can free the space and adjust the pointers to make the linked list still works properly.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /*If queue is empty or NULL*/
    if (q == NULL || q->head == NULL)
        return false;
    /*If sp is non-NULL, copy the string about to be removed to it*/
    /*the maximum copied string size is bufsize-1*/
    if (sp != NULL) {
        strncpy(sp, q->head->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    /*Free the space*/
    list_ele_t *temp = q->head;
    q->head = q->head->next;
    free(temp->value);
    free(temp);
    q->size--;
    return true;
}

q_size

Expected Functionality

• Calculate and return the current size of this queue
• Return 0 if queue is empty or non-existing
• This function should be implemented in O(1)

Code

Instead of calculating the size in this function, we record the size of the queue everytime we insert or remove an element. To do so, we need to declare an integer called size in the queue structure.
You can go and check the code above, there is a line q->size--; or q->size++; everytime we remove or insert an element.
In this case, the code is so simple as below:

int q_size(queue_t *q)
{
    if (q == NULL) {
        return 0;
    }
    return q->size;
}

q_reverse

Expected Functionality

• Reverse the element sequence in queue
• The function should not allocate or free any list element

Code

First, we handle the special cases, empty queue and non-existing queue. In this two cases, we don't need to do anything.
Then, we use three pointers here, which are prev, temp, and next. prev holds the element previous to temp, and next holds the one next to temp. We go through the whole list from the head and make the element holded by temp point to previous one, then move to the next element by using next. This move will keep being implemented until temp reaches NULL.

void q_reverse(queue_t *q)
{
    /*Handle empty queue and non-existing queue*/
    if (q == NULL || q->head == NULL)
        return;

    list_ele_t *temp, *prev, *next;
    prev = q->head;
    temp = prev->next;
    next = temp;
    q->head->next = NULL;
    q->tail = q->head;
    while (temp != NULL) {
        next = temp->next;
        temp->next = prev;
        prev = temp;
        temp = next;
    }
    q->head = prev;
    return;
}

Result

e24046616@tommywang-MacBookPro:~/lab0-c$ make test
scripts/driver.py
---     Trace           Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---     trace-01-ops    6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
---     trace-02-ops    6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
---     trace-03-ops    6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
---     trace-04-ops    6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
---     trace-05-ops    6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
---     trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
This queue doesn't exist!
This queue doesn't exist!
---     trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
---     trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
---     trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
can't allocate space for the queue.
can't allocate space for the queue.
---     trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
Couldn't allocate space for the string!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
---     trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the string!
Couldn't allocate space for the element!
Couldn't allocate space for the element!
---     trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
---     trace-13-perf   7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
---     trace-14-perf   7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
---     trace-15-perf   7/7
---     TOTAL           100/100

How does the testing system work

I'm new to linux, so all these stuff are totally unfailliar for me. I'm not sure I can really well elaborate how this system work, but I'll write down what I learned and try my best to explain it.

Makefile

Reference: Linux make command

We use the command make to compile and genenrate the executable code. This command is a utility for building and maintaining groups of programs from source code. The make program uses the makefile data base and the last-modification times of the files to decide which of the files need to be updated. For those files, it issues the commands recorded in the database. make executes commands in the makefile, if no -f is present, make will look for the makefiles GNUmakefile, makefile, Makefile, in that order.

Note: The Makefile is recommended becasue it appears prominently near the beginning of a directory listing, right near other improtant files such as README.

Compile the source code

When we do make without any arguments like this in terminal:

make

make builds the first target that appears in its makefile, which is traditionally a target named all. In the Makefile of the homework, it is:

all: $(GIT_HOOKS) qtest

From this target, make will compile the source code and build the executable file qtest by running the command from this line in the Makefile:

qtest: qtest.c report.c console.c harness.c queue.o
	$(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o

We can know it will also generate the Git Hooks if we expand the macro (GIT_HOOKS) and look at the rule:

GIT_HOOKS := .git/hooks/applied
$(GIT_HOOKS):
	@scripts/install-git-hooks
	@echo

Evaluation

According from the pdf file of the homework requirement, the driver program driver.py runs the qtest and computes the score. When we do make with argument test following like this:

make test

make build this target in the Makefile:

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

That is how make invoke the driver.