Try   HackMD

2020q1 Homework1 (lab0)

contributed by < Jadezzz >

作業要求
作業區

queue.h 實作

增加 queue_t 欄位

/* Queue structure */
typedef struct {
    list_ele_t *head, *tail; /* Head and tail of the linked list of elements */
    unsigned long size;      /* Size of the linked list */
} queue_t;

根據作業要求， q_insert_tail 以及 q_size 函數需要達到

O(1) 的時間複雜度，所以對 queue_t 的欄位做以下修改：

  1. 新增 tail 指標記錄 queue 最末端的元素
  2. 新增 size 記錄 queue 當前的大小（因爲 size 不爲負數，使用 unsigned long 能記錄最多
    232−1     個元素）

queue.c 實作

實作 q_new 函數

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    /* Return NULL if malloc failed */
    if (!q)
        return NULL;
    /* Initialization of fields */
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}
  1. 如果 malloc() 執行失敗，則回傳 NULL
  2. 初始化 queue 的各個欄位

實作 q_insert_head 函數

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *value;
    /* Return false if q is NULL */
    if (!q)
        return false;
    /* Allocate space for list_ele_t */
    newh = malloc(sizeof(list_ele_t));
    /* Check if space is allocated */
    if (!newh) {
        return false;
    }
    unsigned int value_length = strlen(s);
    /* Allocate space for string value */
    value = malloc(value_length + 1);
    /* Check if space is allocated */
    if (!value) {
        free(newh);
        return false;
    }
    memset(value, '\0', value_length + 1);
    /* Copy input string to allocated space */
    strncpy(value, s, value_length);
    /* Assign value and change head */
    newh->value = value;
    newh->next = q->head;
    /* If the queue was empty, assign tail pointer to its new head */
    if (q->size == 0) {
        q->head = q->tail = newh;
    } else
        q->head = newh;
    /* Update the size of the queue */
    q->size++;
    return true;
}
  1. 檢查傳入的 q ，如果爲 NULL 則回傳 false
  2. 分別爲新的 list 元素和 value 獲取空間
  3. 分別檢查獲取空間是否失敗，若失敗，則回傳 false
  4. 將傳入的 value 複製到新的 value 空間
  5. 將新的元素串接至原 queue 的前端
  6. 判斷 queue 原先是否爲空:
    • 若爲空則將 head 與 tail 設定爲新的 list 元素
    • 若不爲空則將 head 指向新的 list 元素
  7. 設定 queue 的 head 爲新的 list 元素
  8. 修改 queue 的個數

實作 q_insert_tail 函數

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    char *value;
    /* Return false if q is NULL */
    if (!q)
        return false;
    /* Allocate space for list_ele_t */
    newh = malloc(sizeof(list_ele_t));
    /* Check if space is allocated */
    if (!newh) {
        return false;
    }
    unsigned int value_length = strlen(s);
    /* Allocate space for string value */
    value = malloc(value_length + 1);
    /* Check if space is allocated */
    if (!value) {
        free(newh);
        return false;
    }
    memset(value, '\0', value_length + 1);
    /* Copy input string to allocated space */
    strncpy(value, s, value_length);
    /* Assign value and change head */
    newh->value = value;
    newh->next = q->head;
    /* If the queue was empty, assign tail pointer to its new head */
    if (q->size == 0) {
        q->head = q->tail = newh;
    } else
        q->head = newh;
    /* Update the size of the queue */
    q->size++;
    return true;
}
  1. 檢查傳入的 q ，如果爲 NULL 則回傳 false
  2. 分別爲新的 list 元素和 value 獲取空間
  3. 分別檢查獲取空間是否失敗，若失敗，則回傳 false
  4. 將傳入的 value 複製到新的 value 空間
  5. 判斷 queue 原先是否爲空
    • 若爲空則將 head 與 tail 設定爲新的 list 元素
    • 若不爲空則將新的 list 元素串接在 queue 後端，並將 tail 指向新的 list 元素
  6. 設定 queue 的 tail 爲新的 list 元素
  7. 修改 queue 的個數

實作 q_remove_head 函數

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* Return false if queue is NULL or empty */
    if (!q || q->size == 0) {
        return false;
    }
    /* Extract current queue head */
    list_ele_t *oldh = q->head;
    /* Change queue head to next element */
    if (q->size == 1) {
        /* If the queue only got 1 element */
        q->head = q->tail = NULL;
    } else {
        q->head = oldh->next;
    }
    q->size--;
    /* Copy removed string to sp if sp exists*/
    if (sp) {
        strncpy(sp, oldh->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    /* Free old value space and list element space*/
    free(oldh->value);
    free(oldh);
    return true;
}
  1. 若 q 爲 NULL 或者 queue 個數爲 0 則回傳 false
  2. 從原 queue 中取出將移除的元素 oldh
  3. 檢查原 queue 大小
    • 若原 queue 大小爲 1，則把原 queue 的 head 和 tail 指向 NULL
    • 若原 queue 大小不爲 1，則把原 queue 的 head 指向 oldh 的下一個元素
  4. 根據題目要求，若 sp 不爲空，則把原 value 存入 sp 中
  5. 將 oldh->value 的記憶體空間釋放
  6. 將 oldh 本身的記憶體空間釋放

實作 q_free 函數

void q_free(queue_t *q)
{
    /* If queue is NULL, no need to free */
    if (!q) {
        return;
    }
    /* Extract first element */
    list_ele_t *cur = q->head;
    list_ele_t *tmp = NULL;
    while (cur) {
        tmp = cur;
        cur = cur->next;
        /* Free value space */
        free(tmp->value);
        /* Free element structure */
        free(tmp);
    }
    /* Free queue structure */
    free(q);
}
  1. 若傳入的 q 爲 NULL ，直接回傳
  2. 將每個 element 的 value 以及結構釋放
  3. 將 queue 結構釋放

實作 q_reverse 函數

void q_reverse(queue_t *q)
{
    /* q is NULL or empty */
    if (!q || q->size == 0) {
        return;
    }
    /* Queue has only 1 element */
    if (q->size == 1) {
        return;
    }
    /* Initialize prev, curr and next pointers */
    list_ele_t *prev = NULL;
    list_ele_t *curr = q->head;
    list_ele_t *next = NULL;
    /* Reverse the linked list using 3 pointers method */
    while (curr) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    /* Exchange the original head and tail pointers */
    list_ele_t *tmp = q->head;
    q->head = q->tail;
    q->tail = tmp;
    return;
}
  1. 若 queue 爲 NULL 或空，直接回傳
  2. 若 queue 只有 1 個元素，直接回傳
  3. 使用三指針方式進行 linked list 反轉

    圖片來源
  4. 交換原本的 head 和 tail

實作 q_sort 函數

由於題目要求 q_sort

嘗試 1 —— Merge Sort (Recursive split and Recursive merge)

參考 Lisked List Sort 使用 Recursive 的方式進行 split 以及 merge

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    /* Return the other list when one of the list is empty */
    if (!l2)
        return l1;
    if (!l1)
        return l2;
    /* Concat list in ascending order */
    if (strcmp(l1->value, l2->value) < 0) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l1, l2->next);
        return l2;
    }
}

list_ele_t *merge_sort_list(list_ele_t *head)
{
    /*
     * Do nothing if head is NULL
     * or the list has only one element
     */
    if (!head || !head->next)
        return head;
    /* Use fast and slow pointers to seperate the list into two halves */
    list_ele_t *fast = head->next;
    list_ele_t *slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    /* Sort each half of the list */
    list_ele_t *l1 = merge_sort_list(head);
    list_ele_t *l2 = merge_sort_list(fast);
    /* merge sorted lists */
    return merge(l1, l2);
}

void q_sort(queue_t *q)
{
    /* Return if q is NULL or empty or has only one element */
    if (!q || q->size == 0 || q->size == 1)
        return;
    /* Change the head to sorted list */
    q->head = merge_sort_list(q->head);
    /* Change the new tail */
    list_ele_t *tail = q->head;
    while (tail->next) {
        tail = tail->next;
    }
    q->tail = tail;
}

執行 make test 後測試結果，發現 test case 中 只有第 15 個 出現 Segmentation Fault，其餘正常

...
---     trace-15-perf   0/6
+++ TESTING trace trace-16-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
...

查看 trace 後發現第 15 個 test case 會插入 2000000 個元素後進行排序，推測是使用 Recursive 導致 Stack Overflow 造成 Segmentation Fault

# Test performance of insert_tail, size, reverse, and sort
option fail 0
option malloc 0
new
ih dolphin 1000000
it gerbil 1000000
size 1000
reverse
sort
size 1000

使用 make valgrind ，運用 Valgrind 工具檢查記憶體使用狀況，發現果然是 Stack Overflow

...
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, reverse, and sort
==11113== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==11113== Stack overflow in thread #1: can't grow stack to 0x1ffe801000
==11113== Can't extend stack to 0x1ffe8010a8 during signal delivery for thread 1:
==11113==   no stack segment
...

嘗試 2 —— Merge Sort (Recursive split and Iterative merge)

將 merge 的部分改用 Iterative 方式，減少 stack 的使用量，避免 stack overflow

list_ele_t *merge(list_ele_t *l1, list_ele_t *l2)
{
    /* Concat list in ascending order iteratively */
    list_ele_t *head = NULL;
    list_ele_t *cur = NULL;
    /* While l1 and l2 both have elements */
    while (l1 && l2) {
        if (strcmp(l1->value, l2->value) < 0) {
            if (!head) {
                head = cur = l1;
            } else {
                cur->next = l1;
                cur = cur->next;
            }
            l1 = l1->next;
        } else {
            if (!head) {
                head = cur = l2;
            } else {
                cur->next = l2;
                cur = cur->next;
            }
            l2 = l2->next;
        }
    }
    /* Concat the rest of the list */
    if (!l1)
        cur->next = l2;
    if (!l2)
        cur->next = l1;
    return head;
}
  1. 使用 head 記錄 merge 過後的 linked list 起始位置
  2. 使用 cur 記錄 merge 過程中 linked list 的最後一個 element 位置
  3. 在 l1 和 l2 都還沒有被使用完時，將 value 比較小的接在 cur 後
  4. 當 l1/l2 其中一個用完時，將剩下的接在 cur 後

變更排序方法爲 natural sort

使用 natsort 方式實作

strcmp v.s. natural sort

C99 規格書，7.21.4 Comparison functions 可以找到 strcmp 比較的原則：

The sign of a nonzero value returned by the comparison functions memcmp, strcmp,
and strncmp is determined by the sign of the difference between the values of the first
pair of characters (both interpreted as unsigned char) that differ in the objects being
compared.

也就是說，strcmp 比較的原則是將兩個 string 內容以 unsigned char 比對，當碰到不一樣的 unsigned char 時，就返回 unsigned char 相差的值

e.g.

strcmp("a", "b");

返回值爲 -1，因爲 a 的 ASCII code - b 的 ASCII code 結果爲 -1

以爲這樣的機制，所以考慮以下的三個子串 rfc1.txt、rfc2086.txt、rfc822.txt

如果以 strcmp 作爲排序依據，則結果爲：

rfc1.txt < rfc2086.txt < rfc822.txt

但是通常我們希望 數字部分能按照大小進行排列，所以使用 natural sort

natural sort 的機制是：

Strings are sorted as usual, except that decimal integer substrings are compared on their numeric value.

所以考慮上述的子串，使用 natural sort 結果爲：

rfc1.txt < rfc822.txt < rfc2086.txt

將 natural sort 整合

  1. 從 natsort 中下載 strnatcmp.h 和 strnatcmp.c 並加入專案目錄
  2. 修改 Makefile，使 strnatcmp.c 被編譯 
    ​​​​--- a/Makefile
​​​​+++ b/Makefile
​​​​@@ -25,7 +25,7 @@ $(GIT_HOOKS):
​​​​        @scripts/install-git-hooks
​​​​        @echo

​​​​-OBJS := qtest.o report.o console.o harness.o queue.o \
​​​​+OBJS := qtest.o report.o console.o harness.o queue.o strnatcmp.o \
​​​​         random.o dudect/constant.o dudect/fixture.o dudect/ttest.o
​​​​ deps := $(OBJS:%.o=.%.o.d)
  3. 在 q_sort() 函數中，變更原 strcmp 爲 strnatcmp
Last changed by 
 
Robin Lin
0
526
Published on HackMD