2020q1 Homework1 (lab0)

contributed by < DaDa0413 >

其他學習心得: Makefile閱讀筆記

queue.c實做

前面6個 function 花一點時間便完成，但 q_sort() 重做了1次又debug一整天

中英文之間需要以一個半形空白字元區隔 (即 )，在作業要求已清楚描述，務必遵守。
快去改！

jserv

q_new()

建立一個新的 Empty queue

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    // If nothing return by malloc, just return NULL
    if (q == NULL) {
        printf("ERROR: q_new() failed\n");
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    printf("INFO: q new success\n");
    return q;
}

q_free()

除了要釋放 queue 的 header ，也要釋放所有 list element 的記憶體空間。

void q_free(queue_t *q)
{
    // Free all the list element and the head of the queue
    if (q == NULL) {
        return;
    }

    list_ele_t *current_ptr = q->head;
    list_ele_t *next = NULL;
    while (current_ptr != NULL) {
        next = current_ptr->next;
        // Free the memory used by string and list elements
        free(current_ptr->value);
        free(current_ptr);
        current_ptr = next;
    }
    free(q);
}

q_insert_head()

遇到 NULL queue 便直接回傳false。
否則便回傳true分配記憶體給新的element，以及維護queue的架構。

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        printf("ERROR: Insert head to a NULL queue\n");
        return false;
    }
    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        // If queue is allocated at this time
        printf("ERROR: allocate newh fail\n");
        return false;
    }
    unsigned int s_lenth = strlen(s);
    newh->value = malloc(sizeof(char) * (s_lenth + 1));
    // If fail to allocate space for value
    if (newh->value == NULL) {
        printf("ERROR: allocate newh->value fail\n");
        free(newh);
        // If queue is allocated at this time
        return false;
    }
    strncpy(newh->value, s, s_lenth);
    newh->value[s_lenth] = '\0';
    // Maintain the queue structure
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size += 1;
    return true;
}

q_insert_tail()

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        printf("ERROR: Insert tail to a NULL queue\n");
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }
    unsigned int s_lenth = strlen(s);
    newh->value = malloc(sizeof(char) * (s_lenth + 1));
    // If fail to allocate space for value
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, s_lenth);
    newh->value[s_lenth] = '\0';
    // Maintain the queue structure
    newh->next = NULL;
    if (q->size != 0)
        q->tail->next = newh;
    if (q->size == 0)
        q->head = newh;
    q->tail = newh;
    q->size += 1;
    return true;
}

q_size()

直接在 insert 以及 remove 時紀錄 queue 的大小，來讓 q_size() 能達成 O(1)

int q_size(queue_t *q)
{
    // Return the queue size we take down
    if (q == NULL) {
        printf("ERROR: No size of a NULL queue\n");
        return 0;
    }
    return q->size;
}

q_reverse()

使用current_ptr、prev_ptr和next_ptr，來指向當前的 element ，前一個 element 以及下一個 element ，再將current_ptr的指標方向從next_ptr轉向prev_ptr。當全部的 element 完成以後，再將 queue 的 head 以及 tail 轉向。

void q_reverse(queue_t *q)
{
    if (q == NULL) {
        printf("ERROR: Reverse a NULL queue\n");
        return;
    }
    list_ele_t *prev_ptr = NULL;
    list_ele_t *current_ptr = q->head;
    list_ele_t *next_ptr = NULL;
    while (current_ptr != NULL) {
        next_ptr = current_ptr->next;
        current_ptr->next = prev_ptr;
        prev_ptr = current_ptr;
        current_ptr = next_ptr;
    }
    // Maintain the queue structure
    list_ele_t *tmp = q->tail;
    q->tail = q->head;
    q->head = tmp;
}

修改q_sort()

目前使用的字串比較函式是strcmp()，而排序方法為 bubble sort ，但是當我測試trace-15-perf.cmd時，花了10分鐘仍然跑不出來，因此首先我將會把 strcmp 改成作業說明所提及的 natural sort，

void q_sort(queue_t *q)
{
    // Handling NULL queue
    if (q == NULL) {
        printf("ERROR: q sort a NULL queue\n");
        return;
    }
    // Accroding to ascending order, bubble sort the queue
    list_ele_t *roundend = q->tail;
    while (roundend != q->head) {
        list_ele_t *current = q->head;
        while (current != roundend) {
            /* if current element is bigger than next element
            / then swap the values of the two.
            /
            / Tricky solution: Swap the VALUE instead of LIST ELEMENT,
            / it will reduce several pointer re-assignment into three.
            */
            if (strcmp(current->value, current->next->value) > 0) {
                char *temp;
                temp = current->next->value;
                current->next->value = current->value;
                current->value = temp;
            }
            if (current->next == roundend)
                roundend = current;
            else
                current = current->next;
        }
    }
}

發現 bubble sort 真的慢

，因此改以 iterative merge sort 實作:

1. 以 botton up 的方法，來達成原本要用 recursive 完成的 merge sort。
2. 設定一個變數interval，初始為1，用來表示當前要 merge 的 sub-list 的長度，每一次合併(稱為一個 round )兩個長度為interval的 list ，合併完成後在合併下兩個 sub-list ，當整個 list 的 sub-list 都被合併以後，將interval乘以2，並再重複上述動作
3. 設定了4個 pointer 來引導 merge sort
   • prv:指向上一 round 的最後一個 element
   • nxt:這一 round 的下一個 element
   • cur1:要合併的第一個 sublist
   • cur2:要合併的第二個 sublist
4. 為了避免多餘的記憶體分配，直接將既有的 element 放入暫存的 list ，因此新增了 q_insert_element_to_tail() 。

void q_sort(queue_t *q)
{
    if (q == NULL || q_size(q) == 0 || q_size(q) == 1)
        return;
    // In order to avoid to extra line to handle head element
    // case, we maintain a pseudo head.
    list_ele_t pseudo;
    pseudo.next = q->head;
    for (unsigned int interval = 1; interval < q_size(q); interval *= 2) {
        // prv is the last element of previous round
        // nxt is the first element of next round
        // next_prv will record where prv will move to
        list_ele_t *prv = &pseudo;
        list_ele_t *nxt = pseudo.next;
        while (nxt != NULL) {
            // cur1 and cur2 lead two lists to be sorted
            list_ele_t *cur1 = prv->next;
            list_ele_t *cur2 = cur1;
            for (unsigned int i = 0; cur2 != NULL && i < interval; ++i)
                cur2 = cur2->next;

            // move next_prv and nxt to correct place
            nxt = cur2;
            for (unsigned int i = 0; nxt != NULL && i < interval; ++i)
                nxt = nxt->next;

            queue_t merge = {.head = NULL, .tail = NULL, .size = 0};
            // cur1_end and cur2_end is the next element of each list
            list_ele_t *cur1_end = cur2;
            list_ele_t *cur2_end = nxt;
            while (cur1 != cur1_end || cur2 != cur2_end) {
                if (cur2 == cur2_end ||
                    (cur1 != cur1_end &&
                     strnatcmp(cur1->value, cur2->value) < 0)) {
                    list_ele_t *tmp1 = cur1;
                    cur1 = cur1->next;
                    q_insert_element_to_tail(&merge, tmp1);
                } else {
                    list_ele_t *tmp2 = cur2;
                    cur2 = cur2->next;
                    q_insert_element_to_tail(&merge, tmp2);
                }
            }
            prv->next = merge.head;
            prv = merge.tail;
            merge.tail->next = nxt;
            q->tail = merge.tail;
        }
    }
    q->head = pseudo.next;
}

開發問題

1. Problem:

   ​​​​bool q_insert_head(queue_t *q, char *s)
   

   以及

   ​​​​bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
   

   會出現 char *s 以外的亂碼
   

   
   Solution:
   查閱網路 Cplusplus 上，查閱到 strncpy() 的錯誤使用方法，strncpy() 並不會自動在字串結尾加入'\0'。

   ISO/IEC 9899:201 提到關於 strncpy 的敘述:

   The strncpy function copies not more than n characters (characters that follow a null
   character are not copied) from the array pointed to by s2 to the array pointed to by s1.

   但沒有講明是否有複製 '\0'，因此最後在他人整理過得資料字串長度、複製、串接中得出需要自行加入

   查閱資料需要指明出處，並儘量以第一手資料為主，說好的 C 語言規格書呢？
   

   jserv

2. Problem:
   

   
   Solution:
   使用 Valgrind 分析
   
   
   很明顯的告訴我們，在q_insert_head()被 allocate 的 block 還是 reachable 。因此得知， Free 一個 list element 時，不會將被 allocate 的空間也自動 free 掉，因此必須要
   ​​​​free(list_element->value);
   ​​​​free(list_element);
   

3. Problem:
   執行 trace-07-robust.cmd ，測試 insert head to NULL queue 時，不斷發生 segmentation fault 。即使在q_insert_head()的最後一行加入

   ​​​​printf("%s\n", q->head->value);
   

   仍可以正常的印出字串
   Solution:
   運用 Valgrind ，分析記憶體 Segmentation fault 的原因，發現出錯的地方式在 qtest.c 的

   ​​​​if (!q->head->value) {
   

   開始去思考此 q 跟我在q_insert_head()中引入的q是否視同一個。
   才發現搞錯題目的意思，當insert head或insert tail遇上 NULL queue 時，直接返回 fasle 即可，不須額外的q_new()，因此對q_insert_head()做以下更動

 bool q_insert_head(queue_t *q, char *s)
 {
     /* TODO: What should you do if the q is NULL? */
-    // Dada: Call q_new() and handle the NULL case
-    bool q_was_NULL = false;
     if (q == NULL) {
-        q_was_NULL = true;
-        if ((q = q_new()) == NULL)
-            return false;
+        printf("ERROR: Insert head to a NULL queue\n");
+        return false;
     }

文字訊息不要用圖片展現，可善用 diff -up 輸出程式碼之間的差異。

jserv