2019q1 Homework1 (lab0)

contributed by < lineagech >

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

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

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

jserv

Requirement

Implement linked list's insert/delete, head/tail, new, free, reverse:

q_new: Create a new, empty queue.
q_free: Free all storage 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: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.

Two of the functions: q_insert_tail and q_size will require some effort on your part to meet the required performance standards. Naive implementations would require O(n) steps for a queue with n elements.

We require that your implementations operate in time O(1)

Implementation

queue.h

Due to O(1) time complexity requirement，need to additionally have tail of queue:

/* Queue structure */
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

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)
{
    /* How about freeing the list elements and the strings? */
    if (q == NULL)
        return;
    list_ele_t *curr = q->head;
    while (curr != NULL) {
        list_ele_t *tmp = curr->next;
        free(curr->value);
        free(curr);
        curr = tmp;
    }
    /* Free queue structure */
    free(q);
}

q_insert_head

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

    newh->value = malloc(strlen(s) + 1);
    if (newh->value == NULL)
        return false;
    memcpy(newh->value, s, strlen(s));
    newh->value[strlen(s)] = '\0';

    q->size++;

    return true;
}

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 */
    list_ele_t *newt;
    if (q == NULL)
        return false;

    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    if (q->tail != NULL)
        q->tail->next = newt;
    q->tail = newt;
    if (q->head == NULL)
        q->head = newt;

    newt->next = NULL;
    newt->value = malloc(strlen(s) + 1);
    if (newt->value == NULL)
        return false;
    memcpy(newt->value, s, strlen(s));
    newt->value[strlen(s)] = '\0';

    q->size++;

    return true;
}

q_remove_head

Handling null bytes is easily ignored. When copying from value, we should notice if buffer size is larger or smaller than value length.

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    list_ele_t *target;
    if (q == NULL || q->size == 0)
        return false;
    target = q->head;
    q->head = q->head->next;
    if (q->head == NULL)
        q->tail = NULL;

    if (sp != NULL) {
        size_t value_str_len = strlen(target->value);
        if (value_str_len >= bufsize) {
            strncpy(sp, target->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        } else {
            strncpy(sp, target->value, value_str_len);
            sp[value_str_len] = '\0';
        }
    }
    free(target->value);
    free(target);
    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;
    else
        return q->size;
}

q_reverse

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    list_ele_t *curr = NULL;
    list_ele_t *prev = NULL;

    if (q == NULL)
        return;

    curr = q->head;
    q->tail = curr;
    while (curr != NULL) {
        list_ele_t *tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    q->head = prev;
}

Behaviors and skills in qtest

found that re-define malloc and free：

/* Tested program use our versions of malloc and free */
#define malloc test_malloc
#define free test_free

block_ele_t

• To record size and # of malloc for allocated memory block in double linked list
• Notice there is a zero-length array, that is, Declaring zero-length arrays is allowed in GNU C as an extension. A zero-length array can be useful as the last element of a structure that is really a header for a variable-length object:. So we can know the payload address of continuous memory

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];
    /* Also place magic number at tail of every block */
} block_ele_t;

test_malloc

• fail_allocation() generate allocate memory failed condistion according the probability
• Every time there will be block_ele_t allocated when calling malloc, and put some information like header and footer.

void *test_malloc(size_t size)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to malloc disallowed");
        return NULL;
    }
    if (fail_allocation()) {
        report_event(MSG_WARN, "Malloc returning NULL");
        return NULL;
    }
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    void *p = (void *) &new_block->payload;
    memset(p, FILLCHAR, size);
    new_block->next = allocated;
    new_block->prev = NULL;
    if (allocated)
        allocated->prev = new_block;
    allocated = new_block;
    allocated_count++;
    return p;
}

test_free

• It can be seen that footer is used to detect memory corruption

void test_free(void *p)
{
    if (noallocate_mode) {
        report_event(MSG_FATAL, "Calls to free disallowed");
        return;
    }
    if (p == NULL) {
        report(MSG_ERROR, "Attempt to free NULL");
        error_occurred = true;
        return;
    }
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    memset(p, FILLCHAR, b->payload_size);

    /* Unlink from list */
    block_ele_t *bn = b->next;
    block_ele_t *bp = b->prev;
    if (bp)
        bp->next = bn;
    else
        allocated = bn;
    if (bn)
        bn->prev = bp;

    free(b);
    allocated_count--;
}

Autograde System

When typing make test, it will execute scripts/driver.py to run commands:

for t in tidList:
            tname = self.traceDict[t]
            if self.verbLevel > 0:
                print("+++ TESTING trace %s:" % tname)
            ok = self.runTrace(t)
            maxval = self.maxScores[t]
            tval = maxval if ok else 0
            print("---\t%s\t%d/%d" % (tname, tval, maxval))
            score += tval
            maxscore += maxval
            scoreDict[t] = tval

We can just run each pre-set commands in traceDict and run runTrace for each:

def runTrace(self, tid):
        if not tid in self.traceDict:
            print("ERROR: No trace with id %d" % tid)
            return False
        fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
        vname = "%d" % self.verbLevel
        clist = [self.qtest, "-v", vname, "-f", fname]
        try:
            retcode = subprocess.call(clist)
        except Exception as e:
            print("Call of '%s' failed: %s" % (" ".join(clist), e))
            return False
        return retcode == 0

If something causing wrong, the srcipt will return a flag to rell the score should be counted or not. And finally print the score as we see.