# 2020q3 Homework1 (lab0)
contributed by <`chwchao`>

###### tags: `sysprog2020`

## 實作過程說明

### `queue.h`

/* 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.
     */
    /* TODO: Remove the above comment when you are about to implement. */
} queue_t;

修改結果：

/* Queue structure */
typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    int size;
} queue_t;

* 於 `q_size` 的題目要求中，提及需要實作時間複雜度為 O(1) 的程式，因此本處於結構中加入了 `size` 成員，在增減節點的過程中同時更新，以方便在取得長度時可以有較好的執行效率。
* 於 `q_insert_tail` 的題目要求中，同樣提及目標時間複雜度 O(1)，因此本處亦增加一 `tail` 成員，記錄本 linked list 的最後一節點，當於尾端新增節點時僅需直接插入即可，不需重新遍歷該串列至結尾。

### `queue.c`

#### `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? */
    q->head = NULL;
    return q;
}

修改結果：

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));

    if (q == NULL) {
        return NULL;
    }
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

* 根據題目要求，須判斷記憶體分配是否成功，因此加上一判斷式處理例外狀況。
* 另外根據上述說明，對 `queue_t` 結構我做了一些修改，此處亦應將其他參數一併完成初始化。

#### `q_free`

題目源碼：

/* 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 */
    free(q);
}

修改結果：

void q_free(queue_t *q)
{
    if (q == NULL)
        return;
    while (q->head) {
        list_ele_t *next = q->head->next;
        free(q->head->value);
        free(q->head);
        q->head = next;
    }
    free(q);
}

* 由於 `list_ele_t` 結構中的 `char *value` 是以動態配置其內容，因此此處以一迴圈遍歷串列所有節點，並先釋放 `value` 的記憶體，再行釋放該節點。

#### `q_insert_head`

題目源碼：

/*
 * 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? */
    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? */
    newh->next = q->head;
    q->head = newh;
    return true;
}

修改結果：

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh = malloc(sizeof(list_ele_t));

    if (newh == NULL) {
        return false;
    }
    int len = strlen(s);
    newh->value = malloc((len + 1) * sizeof(char));

    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0) {
        q->tail = newh;
    }
    q->size++;
    return true;
}

* 在新增節點時，由於須配置多項記憶體空間，此處在每次進行 `malloc` 時均重新檢查是否成功。
* 此處值得注意的是，`strlen` 函式回傳的字串長度是不含 '\0' 字元的，但為完整複製該字串，在 `malloc` 及 `strncpy` 的操作上均須再補一字元長度確保空字串的複製及存在。

#### `q_insert_tail`

題目源碼：

/*
 * 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. */
    return false;
}

修改結果：

bool q_insert_tail(queue_t *q, char *s)
{
    if (q == NULL) {
        return false;
    }
    list_ele_t *newh = malloc(sizeof(list_ele_t));

    if (newh == NULL) {
        return false;
    }
    int len = strlen(s);
    newh->value = malloc((len + 1) * sizeof(char));

    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    strncpy(newh->value, s, len + 1);
    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size++;
    return true;
}

* 題目要求以時間複雜度 O(1) 實作，於上方已提到在 `queue_t` 結構中加入 `list_ele_t *tail` 成員方便實作，因此此處可使用該變數並比照 `q_insert_head` 撰寫。

#### `q_remove_head`

題目源碼：

/*
 * 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. */
    q->head = q->head->next;
    return true;
}

修改結果：

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{  
    if (q == NULL) {
        return false;
    }
    if (q->size == 0) {
        return false;
    }
    if (sp) {
        int src_len = strlen(q->head->value);
        if (src_len >= bufsize) {
            strncpy(sp, q->head->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        } else {
            strncpy(sp, q->head->value, src_len);
            sp[src_len] = '\0';
        }
    }
    list_ele_t *next = q->head->next;
    free(q->head->value);
    free(q->head);
    q->head = next;
    q->size--;
    if (q->size == 0) {
        q->tail = NULL;
    }
    return true;
}

#### `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 0;
}

修改結果：

int q_size(queue_t *q)
{
    if (q == NULL) {
        return 0;
    } else {
        return q->size;
    }
}

#### `q_reverse`

題目源碼：

/*
 * 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)
{
    /* TODO: You need to write the code for this function */
    /* TODO: Remove the above comment when you are about to implement. */
}

修改結果：

void q_reverse(queue_t *q)
{ 
    if (q == NULL) {
        return;
    }
    if (q->size == 0) {
        return;
    }

    q->tail = q->head;
    list_ele_t *cursor = NULL;
    while (q->head) {
        list_ele_t *next = q->head->next;
        q->head->next = cursor;
        cursor = q->head;
        q->head = next;
    }
    q->head = cursor;
    return;
}

#### `q_sort`

題目源碼：

/*
 * 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. */
}

修改結果：

void swap_value(list_ele_t *a, list_ele_t *b)
{
    char *tmp = a->value;
    a->value = b->value;
    b->value = tmp;
    return;
}

void quick_sort(list_ele_t *head, list_ele_t *tail, int size)
{
    if (head == NULL || tail == NULL)
        return;
    if (size <= 1)
        return;

    // Get middle node
    list_ele_t *mid = head;
    for (int i = 0; i < size / 2 - 1; ++i) {
        mid = mid->next;
    }

    // Get median of three, and set pivot to tail
    if (strcasecmp(head->value, mid->value) > 0 &&
        strcasecmp(tail->value, mid->value) > 0) {
        mid = strcasecmp(head->value, tail->value) > 0 ? tail : head;
    } else if (strcasecmp(mid->value, head->value) > 0 &&
               strcasecmp(mid->value, tail->value) > 0) {
        mid = strcasecmp(head->value, tail->value) > 0 ? head : tail;
    }
    swap_value(mid, tail);

    // Partition
    int count = 0;
    list_ele_t *process = head;
    list_ele_t *cursor = head;
    list_ele_t *front = NULL;
    while (process != tail) {
        if (strcasecmp(tail->value, process->value) >= 0) {
            swap_value(process, cursor);
            front = cursor;
            cursor = cursor->next;
            count++;
        }
        process = process->next;
    }
    swap_value(cursor, tail);

    quick_sort(head, front, count);
    quick_sort(cursor->next, tail, size - count - 1);
}

void q_sort(queue_t *q)
{
    if (q == NULL || q->size == 0 || q->size == 1)
        return;
    quick_sort(q->head, q->tail, q->size);
    return;
}

## 自動測試執行結果


本次作業中，`qsort` 的實作我首先嘗試以 quick sort 演算法撰寫，同時已考量該演算法 worst case 可高達 O(n^2)，並以 median of three 進行演算法優化。但在 trace-15 的項目中，查看其指令可發現，須對前一百萬筆 `dolphin` 及後一百萬筆 `gerbil` 節點內容進行排序，正好就是 quick sort 的 worst case，因此本次實作若以快速排序法實現 `q_sort`，應較難達到題目要求，目前正重新撰寫 merge sort 版本。