2019q1 Homework1 (lab0)

contributed by <ktvexe>

半夜看還願睡不著，所以試著寫了一下作業。
稍微閱讀程式碼，本來以為是千行的程式，不過後來發現只需要實作 queue.* 的部份，其餘大部份是 UT 的程式碼。

$ cloc .
    34 text files.
    34 unique files.                              
    4 files ignored.

github.com/AlDanial/cloc v 1.74  T=0.17 s (179.9 files/s, 18334.1 lines/s)
--------------------------------------------------------------------------------
Language                      files          blank        comment           code
--------------------------------------------------------------------------------
C                                 5            187            235           1570
DOS Batch                        16             13              0            209
Bourne Again Shell                2             68             67            206
Python                            1             18              2            131
C/C++ Header                      4             88            165            113
Markdown                          1             12              0             35
make                              1              7              0             17
Bourne Shell                      1              5              0             12
--------------------------------------------------------------------------------
SUM:                             31            398            469           2293
--------------------------------------------------------------------------------

cscope

因為長期都使用 server 工作，這次作業回到自己筆電才發現自己筆電的 cscope mapping 壞了，所以紀錄下設定參考連結，讓也是用 vim 的朋友可以參考。

Ref: [Linux] - 將vim打造成source insight

Requirement

實作 FIFO & LIFO queue，整理一下題目要求，並畫重點，總共七組 function 需要實作，其中有提示 q_insert_tail and q_size 要 constant time。

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)

You can do this by including other fields in the queue_t data structure and managing these values properly as list elements are inserted, removed and reversed.

Unit test

$ make test 即可執行 UT，過程中大大小小的問題其實都會被抓出來，像是 NULL pointer dereference, memory leak 等等，最後也會顯示通過的測試數量。

其實也有許多類似的 C UT framework 可以協助開發單元測試，例如 googletest。
Ref: C Unit Test Framework 介紹 (Googletest)

+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR: Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
ERROR:  Removal from queue failed (1 failures total)
ERROR: Freed queue, but 2 blocks are still allocated
ERROR: Freed queue, but 2 blocks are still allocated

...

+++ 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

像 test 06 我就卡了一下，他顯示 Test of truncated strings，其實不好懂是做了什麼測試。

所以 grep 一下找到其測資在 traces/trace-06-string.cmd 中。

$ grep -rn 'Test of truncated strings'
traces/trace-06-string.cmd:1:# Test of truncated strings
Binary file traces/.trace-06-string.cmd.swp matches

用 qtest 逐行執行才知道原來是 reverse 少考慮了只有一個 element 的情況。
因為我是用三個 pointer 來做 reverse，只有一個 element 會造成 dereference null pointer。

# Test of truncated strings
option fail 0
option malloc 0
new
ih aardvark_bear_dolphin_gerbil_jaguar 5
it meerkat_panda_squirrel_vulture_wolf 5
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
option length 30
rh meerkat_panda_squirrel_vulture
reverse
option length 28
rh aardvark_bear_dolphin_gerbil
option length 21
rh aardvark_bear_dolphin
reverse
option length 22
rh meerkat_panda_squirrel
option length 7
rh meerkat
reverse
option length 8
rh aardvark
option length 100 
rh aardvark_bear_dolphin_gerbil_jaguar
reverse
rh meerkat_panda_squirrel_vulture_wolf
free
quit

Implementation

queue.h

增加 data member size & tail for constant time implementation.

/* 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;
    size_t size;

} queue_t;

q_new

要確認 malloc 使否成功。

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{   
    queue_t *q = malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */
    if (q) {
        q->head = NULL;
        q->tail = NULL;
        q->size = 0;
    }
    return q;
}

q_free

linked list 中所有 elements 都需要 free，時間複雜度

$O(n)$。

/* Free all storage used by queue */
void q_free(queue_t *q) 
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (!q)
        return;
    list_ele_t *tmp;

    while (q->head != NULL) {
        tmp = q->head;
        q->head = q->head->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

q_insert_head

comments 中特別強調要為 element 的 string malloc 空間，所以一樣要注意 malloc 失敗時，前面成功要到的空間要 free。

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    if (!q)
        return false;
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    char *ele_val = malloc((strlen(s) + 1) * sizeof(char));
    if (!ele_val) {
        free(newh);
        return false;
    }
    memset(ele_val, '\0', strlen(s) + 1);
    strcpy(ele_val, s);
    newh->value = ele_val;
    newh->next = q->head;

    if (!q->head)
        q->tail = newh;
    q->head = newh;
    q->size++;
    return true;
}

q_insert_tail

同理 q_insert_head

/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
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 *newh;
    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;
    char *ele_val = malloc((strlen(s) + 1) * sizeof(char));
    if (!ele_val) {
        free(newh);
        return false;
    }
    memset(ele_val, '\0', strlen(s) + 1);
    strcpy(ele_val, s);
    newh->value = ele_val;
    newh->next = NULL;

    if (!q->tail) {
        q->head = newh;
        q->tail = newh;
    }
    q->tail->next = newh;
    q->tail = newh;
    q->size++;
    return true;
}

q_remove_head

remove_head 有一個參數 sp ，用以回傳被 delete 掉的 string。(deep copy)
注意有限制長度。

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  If sp is non-NULL and an element is removed, copy the removed string to *sp
  (up to a maximum of bufsize-1 characters, plus a null terminator.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (!q || !(q->head))
        return false;

    list_ele_t *tmp;
    tmp = q->head;
    if (sp) {
        memset(sp, '\0', bufsize);
        strncpy(sp, tmp->value, bufsize - 1);
    }
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    q->size--;
    return true;
}

q_size

回傳 queue 的 size；所以在 add 與 remove 時要記得 maintain size。

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
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)
        return 0;
    return q->size;
}

q_reverse

使用最基本的三個 pointer 來做 reverse。
所以要注意前面的 pointer 走到 null 時，如果繼續 access 會錯誤。

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (!q || !q->head || !q->head->next)
        return;
    list_ele_t *forward, *backward;

    backward = q->head;
    q->tail = q->head;
    q->head = q->head->next;
    forward = q->head->next;
    backward->next = NULL;

    while (forward != NULL) {
        q->head->next = backward;
        backward = q->head;
        q->head = forward;
        forward = forward->next;
    }
    q->head->next = backward;
}

Reference