2021q1 Homework1 (lab0)

contributed by < yuchun1214 >

注意共筆書寫規範：中英文間用一個半形空白字元區隔

jserv

C Programming Lab

queue_t

queue中除了遠本的 list_ele_t *head 以外，我還多加了 list_ele_t *tail 用來指向queue的尾端，以及 int size 來紀錄queue的長度。

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    /* TODO: 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;
    /* TODO: Remove the above comment when you are about to implement. */
} queue_t;

q_new

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

q_free

q_free的功能是將queue清掉。在這裡為了能夠更好的閱讀程式碼，我清掉element的函數另外寫成 void list_ele_free(list_ele_t *ele)

void list_ele_free(list_ele_t *ele)
{
    if (ele) {
        free(ele->value);
        free(ele);
    }
}

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    /* TODO: How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (!q) {
        return;
    }
    list_ele_t *next;
    while (q->head) {
        next = (q->head)->next;
        list_ele_free(q->head);
        q->head = next;
    }
    free(q);
}

q_insert_head

在 insert head 的部分我有點不太滿意自己寫的 code ，主要是底下23行的地放為了能讓 q->tail 能指向正確的位置，但實際上會進入 if 內只會發生在插入第一個 element 時，卻要每次 insert 時都要做 if 的判斷。

/*
 * 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)
{
    list_ele_t *newh;
    /* TODO: What should you do if the q is NULL? */
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    if (q == NULL) {
        return false;
    }
    newh = list_ele_new(s);
    if (!newh)  // fail to malloc
        return false;
    newh->next = q->head;
    q->head = newh;
    ++q->size;
    if (q->tail == NULL) {
        q->tail = q->head;
    }
    return true;
}

q_insert_tail

由於有天在 queue_t 中添加 tail 因此能夠很輕鬆的將 element 加入 queue 中。

/*
 * 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)
{
    /* TODO: You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    /* TODO: Remove the above comment when you are about to implement. */
    if (q == NULL) {
        return false;
    }
    list_ele_t *newt;
    newt = list_ele_new(s);
    if (!newt)
        return false;
    if (q->tail) {
        q->tail->next = newt;
    } else {
        q->head = newt;
    }
    q->tail = newt;
    ++q->size;

    return true;
}

q_remove_head

這個函數比較需要注意的是 line 18 ，因為 strncpy 並不會加上 \0 因此要自己加上

/*
 * 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)
{
    /* TODO: You need to fix up this code. */
    /* TODO: Remove the above comment when you are about to implement. */
    if (q && q->size) {
        list_ele_t *head = q->head;
        q->head = q->head->next;
        if (sp) {
            strncpy(sp, head->value, (bufsize - 1) * sizeof(char));
            sp[bufsize - 1] = '\0';
        }
        --q->size;
        list_ele_free(head);
        return true;
    }
    return false;
}

q_size

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    /* TODO: Remove the above comment when you are about to implement. */
    return (q) ? q->size : 0;
}

這個函數要求要在

$O(1)$ 內完成。在這個函數裡用了一個operator來做判斷，就程式面上來看應該是

$O(1)$ ，但不知為何， make test 量測的結果卻不一定是constant time.於是我決定去看一下組合語言。

從組合語言看起來只差一個 mov 的 instruction 而已，但卻被判斷不一定是常數時間。

q_reverse

實作的原理主要是將每個 element 的 next 指標轉向，指向前一個 element(line:12)

void q_reverse(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* TODO: Remove the above comment when you are about to implement. */
    if (!q || q->size == 0)
        return;
    list_ele_t *prev = q->head;
    list_ele_t *iter = q->head->next;
    list_ele_t *next;
    while (iter && iter->next) {
        next = iter->next;
        iter->next = prev;
        prev = iter;
        iter = next;
    }

    if (!iter)
        return;

    iter->next = prev;

    // swap head and tail
    next = q->tail;
    q->tail = q->head;
    q->head = next;
    q->tail->next = NULL;
}

q_sort

在 q_sort 中原本我有嘗試 quick sort ，但後來想一想會了求穩定還是轉為使用 merge sort ，不過如果實際去看queue.c還是看得到 quick sort code 。

merge sort中主要分兩部分，分別是 list_merge_sort 以及 list_merge ，前者主要做拆分的動作，後者則是做merge。

list_ele_t *list_merge(list_ele_t *lhs, list_ele_t *rhs, list_ele_t **tail)
{
    list_ele_t *result, *result_iter;

    if (strcmp(lhs->value, rhs->value) < 0) {
        result = lhs;
        lhs = lhs->next;
    } else {
        result = rhs;
        rhs = rhs->next;
    }

    result_iter = result;

    while (lhs && rhs) {
        if (strcmp(lhs->value, rhs->value) < 0) {
            result_iter->next = lhs;
            lhs = lhs->next;
        } else {
            result_iter->next = rhs;
            rhs = rhs->next;
        }
        result_iter = result_iter->next;
    }
    while (lhs) {
        result_iter = result_iter->next = lhs;
        lhs = lhs->next;
    }
    while (rhs) {
        result_iter = result_iter->next = rhs;
        rhs = rhs->next;
    }
    *tail = result_iter;
    return result;
}

list_ele_t *list_merge_sort(list_ele_t *head, list_ele_t **tail)
{
    if (!head || !(head->next))
        return head;

    list_ele_t *fast = head->next;
    list_ele_t *slow = head;

    // find the middle of list
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    fast = slow->next;
    slow->next = NULL;

    list_ele_t *lhs = list_merge_sort(head, tail);
    list_ele_t *rhs = list_merge_sort(fast, tail);

    return list_merge(lhs, rhs, tail);
}

/*
 * Sort elements of queue in ascending order
 * No effect if q is NULL or empty. In addition, if q has only one
 * element, do nothing.
 */
void q_sort(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* TODO: Remove the above comment when you are about to implement. */
    // list_quick_sort(&q->head, &q->tail);
    if (q) {
        q->head = list_merge_sort(q->head, &q->tail);
    }
    return;
}

總結以上函數有仔細寫大概都可以拿到100分。

Address Sanitizer

在 make SANITIZER=1 並執行qtest help之後可清楚看見一些錯誤的訊息，訊息指出是 do_help_cmd 函數出錯。

但經肉眼檢查發現應該沒什麼問題，因此轉而檢查 add_param 以及呼叫 add_param 的code，發現問題可能是出現在這裏做的將 int* 指向 bool* 的問題，於是加以修改之後就沒問題了

Valgrind

在 make valgrind 後可以看到一系列的錯問訊息指出有記憶體是 unreachable 。

實際去找出錯誤訊息的程式發現是 strdup 在搞鬼

strdup manual 中是這樣寫的：

於是我認為應該是history最後沒有清掉記憶體，但在 static void freeHistory(void) 中卻有寫到。

於是我開始懷疑是否是因為 history 是 global variable 的關係，因而 valgrind 在檢查時是依照函數內容去做檢查，並非全面性的檢查所有的記憶體。 但這部分仍有待確認… 經過確認後發現， valgrind 的行為並非上述所說。原本我的作法是在 .valgrindrc 中加上 --show-reachable=no ，但這方式有點鴕鳥心態，這樣只是假裝看不到錯誤，並非錯誤消失了。在確認 valgrind 的行為後我決定找出原因。在 linenoise.c 中，原開發者的確有寫到 freeHistory 這些程式碼的內容沒錯，關鍵的原因在於當使用 .cmd 檔案當作輸入時，程式完全不會呼叫 freeHistory 。最簡單的解法就是在 console.c:run_console 結束前呼叫 freeHistory 即可。