# 2020q3 Homework1 (lab0)
contributed by < [`Noahnut`](https://github.com/Noahnut/lab0-c) >

### 開發環境

$ uname -a
Linux ubuntu 5.4.0-47-generic #51-Ubuntu SMP Fri Sep 4 19:50:52 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0

### Lab0 實作過程
* 根據作業要求 `q_insert_tail` 與 `q_siz` 需要在 $O(1)$ 內完成，所以在 `queue.h` 中的 `queue_t` 結構中新增 `tail` 與 `size` 兩個成員。

* #### `queue.h`

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;

    size_t size;
} queue_t;

### [bool q_insert_head(queue_t *q, char *s)](https://github.com/Noahnut/lab0-c/blob/master/queue.c#L48)
> 新增一個型態為 list_ele_t 的 element 並將 queue 的 header . > 指向這個新增的 element 。

* `malloc` element 的 value 時，`strlen` 並不會將 `\0` 算進去過必須要在 `strlen` 後再加一。
* 原本將傳入的字串複製給 `list_ele_t` 的 value 是用 `strcpy` 但在 `git commit -a` 時提醒，這並不是個安全的 function。

char *strcpy(char *dst, const char *src); 

`strcpy` 再將 `src` 字串複製給 `dst`，結束的條件為是否到 `src` 的尾端，在這樣的情況下，如果 `src` 的長度大於 `dst` 就會有 `buffer overflow` 造成程式有非預期的行為。
而 `strncpy`，雖然有限制複製的長度，但不會去檢查 `dst` 的長度，在錯誤的使用下也會造成跟 `strcpy` 相同的狀況。
為了避免這個狀況，使用了 `strcpy` 的安全版本 `strlcpy` 但在目前環境下編譯發生 `strlcpy` 並不在 `string.h` 中，才發現 `strlcpy` 並不在 `glibc` 中，必須要另外引用 `BSD` 的函式庫。
在查關於為什麼 `strlcpy` 為什麼沒有加入到 `glibc` 時發現一則關於 glibc 為什麼不將 `strlcpy`加入的 [文章](https://lwn.net/Articles/612244/) 與當時提交的 [request](https://sourceware.org/legacy-ml/libc-alpha/2000-08/msg00070.html)。

Christoph Hellwig 再將 `strlcpy` 與 `strlcat` 這兩個取代 `strcpy` 與 `strcat` 的函式更新到 `glibc` 時被當時 `glibc` 的維護者 Ulrich Drepper 所拒絕了，Ulrich Drepper 拒絕的原因為

>This is horribly inefficient BSD crap. Using these function only leads to other errors. Correct string handling means that you always know how long your strings are and therefore you can you memcpy (instead of strcpy).
Beside, those who are using strcat or variants deserved to be punished.

大意為
>正確的字串處理應該為永遠都知道您的字串長度大小為何，那您就可以用 `memcpy` 取代 `strcpy` 此在使用 `strcat` 或類似 function 的都該受到處罰。
>

而在文章中提到大部分的設計師對於這個 function 設計不滿，主要是因為這個 function 回傳的是 `src` 字串的長度，如果有粗心的設計師將不會發現 `dst` 是個被截斷的字串，這樣一樣會造成程式的非預期行為。

部分的人覺得這個 function 的設計，能夠提供一個簡單的 API 去做字串複製並且能夠避免 buffer overflow。

看過 source code 跟討論串後，發覺 `string` 處理在 C 中 (或者各個語言) 都是個大議題，只是在各個不同 API 使用上效能 跟 code 易讀之間的取捨，而安全性的部分不管 API 如何設計，設計不良的程式都有可能造成漏洞。

/*
 * Copy string src to buffer dst of size dsize.  At most dsize-1
 * chars will be copied.  Always NUL terminates (unless dsize == 0).
 * Returns strlen(src); if retval >= dsize, truncation occurred.
 */
size_t
strlcpy(char * __restrict dst, const char * __restrict src, size_t dsize)
{
	const char *osrc = src;
	size_t nleft = dsize;

	/* Copy as many bytes as will fit. */
	if (nleft != 0) {
		while (--nleft != 0) {
			if ((*dst++ = *src++) == '\0')
				break;
		}
	}

	/* Not enough room in dst, add NUL and traverse rest of src. */
	if (nleft == 0) {
		if (dsize != 0)
			*dst = '\0';		/* NUL-terminate dst */
		while (*src++)
			;
	}

	return(src - osrc - 1);	/* count does not include NUL */
}

在這個 lab 中我最後使用 `snprintf` 來實作字串複製

int snprintf ( char * s, size_t n, const char * format, ... );

n 為指定 s (目標 buffer) 的大小，將格式化的字串存入 `s` 中，因為有限制 buffer 的大小，如果不是故意的就不會有 buffer overflow 的問題。

複製完字串後，就將這個新的 element 的 next 指向現在的 header，然後再將 header 換成這個新的 element。

### [bool q_insert_tail(queue_t *q, char *s)](https://github.com/Noahnut/lab0-c/blob/master/queue.c#L88)

這裡的實作方式與 `q_insert_head` 類似，差別為新增的 element 是由現有 `queue` 的 `tail` 的 `next` 指向新增的 element 並將 `tail` 換成新增的 element，要注意的部分為如果當 `queue` 為空的時候，也要順便將 `head` 指向新增的 element。

### [q_remove_head(queue_t *q, char *sp, size_t bufsize)](https://github.com/Noahnut/lab0-c/blob/master/queue.c#L130)
將目前 `queue` 的 head 刪掉，實作方法就將目前 head 指向的 element 換成下一個，並且將要刪掉的 element 與原先 `malloc` 的字串所使用的記憶體釋放掉。
而在跑 `make test` 的時候發現 `test7` 會有字串 buffer overflow 的問題，這個時候才發現 在`test7` 的字串長度會超過 buffer size，所以這邊還要再判斷 buffer size。

### [void q_reverse(queue_t *q)](https://github.com/Noahnut/lab0-c/blob/master/queue.c#L160)
實作的想法，是將我目前指向的 element 的 next element，原本的 next 反轉指向我目前指向的 element，然後在將目前指向的 element 換成被反轉的那個 element，這邊要注意的是因為 next element 的 next 已經被反轉，所以要先將其被反轉前的 next element 記錄下來，最後再將 head 與 tail 交換。

### [void q_sort(queue_t *q)](https://github.com/Noahnut/lab0-c/blob/master/queue.c#L262)
這個做 linked list 的 sorting 的方式用 Merge Sort，Merge Sort 的最基本原理為 Divide and Conqure ，因為 queue 為 Singly Linked List 不能直接用最原本 Merge Sort 的方式從中間切開，所以我利用 Fast and Slow clock 的方式去找到 Linked List 的中間。
Merge 的部分最原先是用 `recursice` 的方式去實作，但是在跑 `test15` 發現有 `stack overflow` 的問題，所以就改成非遞迴的方式。

### is q_size and q_insert_tail is constant time ?
最主要判斷 `q_size` 與 `q_insert_tail` 是否為 `const time` 的函式分別為`is_size_const` 與 `is_insert_tail_const`，而這兩個函式是用 `Dude, is my code constant time` 中的方式
* 1. 準備兩種資料 `random value` 與 `const value` 的資料