# 2021q1 Homework1 (lab0)
contributed by < `D4nnyLee` >

## 實做 queue.[ch]

看過許多人的實做方法後，我在思考如何不在 `queue_t` 中新增 `tail` 變數也可以使 `q_insert_tail()` 的時間複雜度為 $O(1)$ 。
而我目前得到的答案為 [Circular Singly Linked List](https://www.javatpoint.com/circular-singly-linked-list)
:::warning
很好，你已經發現 Linux 核心原始程式碼的設計考量了，對照看 Linux 程式碼來觀察其 circular linked list 的使用。
:notes: jserv
:::

以下用幾個圖例來畫出實際的結構：

> 這邊利用 qtest 的指令來表達做了什麼動作
1. `new`

    digraph {
		head [shape = ellipse]
		dummy [shape = box]
		
		head -> dummy
		dummy -> dummy [label = " next"]
	}

2. `ih abc`

    digraph {
		head [shape = ellipse]
		dummy [shape = box]
		abc [shape = box]
		
		head -> dummy
		{
			rank = same
			dummy -> abc [label = " next"]
			abc -> dummy [label = " next", constraint = false]
		}
	}

3. `it def`

    digraph {
		head [shape = ellipse]
		dummy [shape = box]
		abc [shape = box]
		def [shape = box]
		
		head -> dummy
		{
			rank = same
			dummy -> abc [label = " next"]
			abc -> def [label = " next"]
			def -> dummy [label = " next"]
		}
	}

但是原本的 qtest.c 的檢查機制不允許 linked list 有環，且我的實做方式有使用到 [Dummy Node](https://algorithm.yuanbin.me/zh-tw/basics_data_structure/linked_list.html#dummy-node) 的技巧，因此第一筆存進來的資料不是存在 `queue_t` 中的 `head` 節點，而是存在 `head->next` 節點。

因此我對 qtest.c 做了以下修改，讓檢查符合我的結構的邏輯。
> 可能需要改的地方不只這些，如果有發現其他需要改的歡迎在以下提出。

@@ -215,7 +215,7 @@ static bool do_insert_head(int argc, char *argv[])
             bool rval = q_insert_head(q, inserts);
             if (rval) {
                 qcnt++;
-                if (!q->head->value) {
+                if (!q->head->next->value) {
                     report(1, "ERROR: Failed to save copy of string in list");
                     ok = false;
                 } else if (r == 0 && inserts == q->head->value) {
@@ -224,14 +224,14 @@ static bool do_insert_head(int argc, char *argv[])
                            "list element");
                     ok = false;
                     break;
-                } else if (r == 1 && lasts == q->head->value) {
+                } else if (r == 1 && lasts == q->head->next->value) {
                     report(1,
                            "ERROR: Need to allocate separate string for each "
                            "list element");
                     ok = false;
                     break;
                 }
-                lasts = q->head->value;
+                lasts = q->head->next->value;
             } else {
                 fail_count++;
                 if (fail_count < fail_limit)
@@ -300,7 +300,7 @@ static bool do_insert_tail(int argc, char *argv[])
             bool rval = q_insert_tail(q, inserts);
             if (rval) {
                 qcnt++;
-                if (!q->head->value) {
+                if (!q->head->next->value) {
                     report(1, "ERROR: Failed to save copy of string in list");
                     ok = false;
                 }
@@ -358,7 +358,7 @@ static bool do_remove_head(int argc, char *argv[])
 
     if (!q)
         report(3, "Warning: Calling remove head on null queue");
-    else if (!q->head)
+    else if (q->head->next == q->head)
         report(3, "Warning: Calling remove head on empty queue");
     error_check();
 
@@ -424,7 +424,7 @@ static bool do_remove_head_quiet(int argc, char *argv[])
     bool ok = true;
     if (!q)
         report(3, "Warning: Calling remove head on null queue");
-    else if (!q->head)
+    else if (q->head->next == q->head)
         report(3, "Warning: Calling remove head on empty queue");
     error_check();
 
@@ -558,7 +558,8 @@ bool do_sort(int argc, char *argv[])
 
     bool ok = true;
     if (q) {
-        for (list_ele_t *e = q->head; e && --cnt; e = e->next) {
+        for (list_ele_t *e = q->head->next; e != q->head && --cnt;
+             e = e->next) {
             /* Ensure each element in ascending order */
             /* FIXME: add an option to specify sorting order */
             if (strcasecmp(e->value, e->next->value) > 0) {
@@ -586,9 +587,9 @@ static bool show_queue(int vlevel)
     }
 
     report_noreturn(vlevel, "q = [");
-    list_ele_t *e = q->head;
+    list_ele_t *e = q->head->next;
     if (exception_setup(true)) {
-        while (ok && e && cnt < qcnt) {
+        while (ok && e != q->head && cnt < qcnt) {
             if (cnt < big_queue_size)
                 report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value);
             e = e->next;
@@ -603,7 +604,7 @@ static bool show_queue(int vlevel)
         return false;
     }
 
-    if (!e) {
+    if (e == q->head) {
         if (cnt <= big_queue_size)
             report(vlevel, "]");
         else

### `queue_t`

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    int size;
} queue_t;

就像前面提到的，我想要不新增 `tail` 這個變數來完成要求，所以這邊我只多新增了一個 `size` 代表 queue 中有多少筆資料。
> 不包含 Dummy Node

### `ele_new()`

為了讓建立一個新的節點時更便利，不用每次需要一個新的節點的時候都需要寫重複的程式碼。

而回傳值也設計的跟 `malloc()`, `q_new()` 一樣，當無法分配記憶體的時候就回傳 NULL 。

/* Create a new node which stores the content of s.
 * Return NULL if could not allocate space.
 */
static list_ele_t *ele_new(char *s) 
{
    list_ele_t *node = malloc(sizeof(list_ele_t));
    if (!node)
        return NULL;

    node->next = node;
    node->value = NULL;

    if (s) {
        size_t len = strlen(s) + 1;

        node->value = malloc(len);
        if (!node->value) {
            free(node);
            return NULL;
        }

        strncpy(node->value, s, len);
    }   

    return node;
}

### `ele_free()`

釋放利用 `ele_new()` 分配出來的空間。

擷取自 [malloc(3) — Linux manual page](https://man7.org/linux/man-pages/man3/free.3.html)
> The free() function frees the memory space pointed to by ptr,
> which must have been returned by a previous call to malloc(),
> calloc(), or realloc(). Otherwise, or if free(ptr) has already
> been called before, undefined behavior occurs. If ptr is NULL,
> no operation is performed.

可以看到 `free()` 即使傳入的值是 NULL 也不會發生錯誤，因此實作上就可以減少一些 `if` 的使用。

static void ele_free(list_ele_t *node)
{
    if (node)
        free(node->value);
    free(node);
}

### `q_new()`

事先利用 `malloc()` 和 `ele_new()` 來要空間，只要其中一個回傳 NULL (分配空間失敗)，就回傳 NULL 。
且為了防止 Memory Leak ，不管是哪個函式失敗都會利用 `free()`, `ele_free()` 來嘗試釋放空間。

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    list_ele_t *newh = ele_new(NULL);  // dummy node
    /* TODO: What if malloc returned NULL? */
    if (!q || !newh) {
        free(q);
        ele_free(newh);
        return NULL;
    }   

    q->head = newh;
    q->size = 0;

    return q;
}

### `q_free()`

因為整個 linked list 包含了一個 Dummy Node 和 `q->size` 個節點，所以只要跑一個 `q->size + 1` 次的迴圈，每次都用 `ele_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 */
    if (!q)
        return;

    list_ele_t *ele = q->head;
    for (int i = q->size; i >= 0; i--) {  // loop for q->size + 1 times
        list_ele_t *tmp = ele;
        ele = ele->next;
        ele_free(tmp);
    }

    free(q);
}

### `q_insert_head()`

基本的 linked list 插入操作，時間複雜度為 $O(1)$。

1. 初始

	digraph {
		node [shape = box]
		
		head [shape = ellipse]
		many [shape = none, label = "..."]
		newh
		head -> dummy
		{
			rank = same
			dummy -> node_1 -> many -> node_n -> dummy
		}
	}

2. .

	digraph {
		node [shape = box]
		
		head [shape = ellipse]
		many [shape = none, label = "..."]
		newh -> node_1 [color = red]
		head -> dummy
		{
			rank = same
			dummy -> node_1 -> many -> node_n -> dummy
		}
	}

3. .

	digraph {
		node [shape = box]
		
		head [shape = ellipse]
		many [shape = none, label = "..."]
		head -> dummy
		{
			rank = same
			dummy -> newh [color = red]
			newh -> node_1 -> many -> node_n -> dummy
		}
	}

/*
 * 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 = ele_new(s);
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    if (!q || !newh) {
        ele_free(newh);
        return false;
    }

    newh->next = q->head->next;
    q->head->next = newh;
    ++q->size;

    return true;
}

### `q_insert_tail()`

先利用 `q_insert_head()` 在開頭新增一個新的節點，再將此節點與 Dummy Node 交換就可以達成常數時間的實作。

/*
 * 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)
{
    /* Remember: It should operate in O(1) time */
    if (!q_insert_head(q, s))
        return false;

    q->head->value = q->head->next->value;
    q->head->next->value = NULL;
    q->head = q->head->next;

    return true;
}

### `q_size()`

/*
 * Return number of elements in queue.
 * Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    /* Remember: It should operate in O(1) time */
    return q ? q->size : 0;
}

### `q_remove_head()`

因為 `q_size()` 在 Empty Queue 和 NULL Queue 的時候都會回傳 0 ，而在這兩個情況 `q_remove_head()` 要回傳 `false` ，所以就直接利用 `q_size()` 的回傳值來判斷是否回傳 `false` 。

/*
 * 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)
{
    if (!q_size(q))
        return false;

    if (sp && bufsize) {
        strncpy(sp, q->head->next->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    list_ele_t *tmp = q->head->next;
    q->head->next = q->head->next->next;
    --q->size;

    ele_free(tmp);

    return true;
}

### `q_reverse()`

因為我實作的是 Circular Singly Linked List ，所以反轉就相當於把每一條邊指向前一個節點，且不用特別維護 `q->head` 的值，因為反轉前和反轉後的 `q->head` 應該是要一樣的。

/*
 * 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)
{
    list_ele_t *node, *next, *prev;
    if (!q)
        return;

    prev = q->head;
    node = prev->next;
    next = node->next;
    for (int i = q->size; i >= 0; i--) {  // loop for q->size + 1 times
        node->next = prev;
        prev = node;
        node = next;
        next = node->next;
    }
}

以下用 `q->size == 3` 的例子一步一步視覺化執行過程：
> `prev`: 黃色
> `node`: 紅色
> `next`: 藍色
> 更動到的邊: 紅色

1. 初始

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		{
			rank = same
			dummy -> a -> b -> c -> dummy
		}
	}

2. `i = 3`

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		dummy [color = yellow, style = filled]
		a [color = red, style = filled]
		b [color = blue, style = filled]
		{
			rank = same
			dummy -> a
			a -> b [color = white]
			b -> c
			c -> dummy
			a -> dummy [color = red]
		}
	}

3. `i = 2`

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		a [color = yellow, style = filled]
		b [color = red, style = filled]
		c [color = blue, style = filled]
		{
			rank = same
			dummy -> a
			a -> b [color = white]
			b -> c [color = white]
			c -> dummy
			a -> dummy
			b -> a [color = red]
		}
	}

4. `i = 1`

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		b [color = yellow, style = filled]
		c [color = red, style = filled]
		dummy [color = blue, style = filled]
		{
			rank = same
			dummy -> a
			a -> b [color = white]
			b -> c [color = white]
			a -> dummy
			b -> a 
			c -> b [color = red]
		}
	}

5. `i = 0`

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		c [color = yellow, style = filled]
		dummy [color = red, style = filled]
		a [color = blue, style = filled]
		{
			rank = same
			dummy -> a [color = white]
			a -> b [color = white]
			b -> c [color = white]
			a -> dummy
			b -> a 
			c -> b 
			dummy -> c [color = red, constraint = false]
		}
	}

也等同於

	digraph {
		node [shape = box]
		head [shape = ellipse]
		head -> dummy
		{
			rank = same
			dummy -> c -> b -> a -> dummy
		}
	}

### `q_sort()`

我的作法為典型的 Merge Sort ，並且有使用到遞迴呼叫，所以我需要先寫另一個 `merge_sort()` 函式來幫助我做到遞迴呼叫。

/*
 * Sort elements in range (beg, end)
 * Note: not in [beg, end)
 */
static void merge_sort(list_ele_t *beg, list_ele_t *end)
{
    if (beg->next == end || beg->next->next == end)  // length <= 1
        return;

    list_ele_t *slow = beg->next, *left, *right, *left_end;
    for (list_ele_t *fast = slow; fast->next != end && fast->next->next != end;
         fast = fast->next->next)
        slow = slow->next;

    merge_sort(slow, end);
    left_end = right = slow->next;

    merge_sort(beg, right);
    left = beg->next;

    for (; left != left_end || right != end; beg = beg->next) {
        if (right == end ||
            (left != left_end && strcasecmp(left->value, right->value) <= 0)) {
            beg->next = left;
            left = left->next;
        } else {
            beg->next = right;
            right = right->next;
        }   
    }

    beg->next = end;
}

呼叫 `merge_sort(beg, end)` 代表是要排序 `(beg, end)` 區間的節點，這裡是使用左開右開區間（不同於常見的左閉右開），並且將排序完的節點與 `beg`, `end` 串接起來。

最後的 `for` 迴圈就兼顧了合併兩個小的已排序 list 與串接排序完節點與 `beg`, `end` 。