# 2019q1 Homework1 (lab0)
Contributed by < [`krimson8`](https://github.com/krimson8) >
:::warning
既然是第二次進行此作業，請考慮下述改進:
1. 引入 [AddressSanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer) 來檢驗記憶體操作，較新版本的 gcc 已包含相關的 sanitizer，搭配 [Useful GCC address sanitizer checks not enabled by default](https://kristerw.blogspot.com/2018/06/useful-gcc-address-sanitizer-checks-not.html);
2. 嘗試保有原本的自動評分系統，將給定的 linked list 程式碼換為 [F02: list](https://hackmd.io/s/S12jCWKHN) 給定的 Linux-like 實作，並確保能夠通過完整的檢驗流程;
3. 重新整理下方共筆 (刪去過時資訊)，學習技術文件的撰寫，可參照 [基於 C 語言標準研究與系統程式安全議題](https://hackmd.io/s/S15o_K3cQ) 的風格;
:notes: jserv
:::
## 實驗環境資訊
```
$ uname -a
Linux pc 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
```
<!-- >* 請補上實驗環境資訊
>* 也請你在重新調整共筆內容，包含 ~~刪除線~~ 的內容以及你提出的疑問和解法
>* 在 commit [b79dd3f](b79dd3ff17876e674571b6a12d2c49c6e0e11305) 中，只需要提及做了哪些修改，不需要提及 test 11, 12 過不了
>
>[name=課程助教][color=red] -->
:::success
100/100
:::
## C-programming lab 作業重點節錄
* 1.Logistics
* 只要linked list 的邏輯正確便不難
* 2.Overview
* 所測試的技能
* Explicit memory management, as required in C.
* Creating and manipulating pointer-based data structures.
* Working with strings.
* Enhancing the performance of key operations by storing **redundant information in data structures.**
* Implementing robust code that **operates correctly with invalid arguments, including NULL pointers.**
* 需要 implement **LIFO 和 FIFO 的 queue** 資料結構
* 3.Resources
* **C programming**
* K&R C
* https://en.wikibooks.org/wiki/C_Programming.
* **Linked lists**
* http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf
* **Asympotic notation**
* http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/05-sort.pdf
* **Linux Man Pages**
* 4, 5 爲 autolab 相關，忽略
* 6.Overview
* `queue.h`
* `list_ele_t` 爲 linked list 的節點 struct
* `queue_t` 爲 queue 的 struct
```clike
/* Linked list element */
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
} queue_t;
```
詳細 queue 結構如下圖：
* 一個**長度爲 L 的 string**，在 C語言 裏面的表達方式爲 **L+1 長度的 char 陣列**
* `list_ele_t` 內的 `value` 應該存有指向一個char array 的 pointer
* `queue_t` 裏的每一個節點都應該有自己的 string （就算和別的節點是一樣的 string）
* 每一個節點都 使用 [strdup](http://man7.org/linux/man-pages/man3/strdup.3.html) 或自行 `malloc`
* 因爲 `strdup` 有使用到 `malloc` 所以猜想刪除節點的時候也要一併`free`掉
* 網絡上找到一個很好的解釋 `strcpy`和 `strdup` 之間的差別
```clike=
// strcpy
while(*ptr2++ = *ptr1++)
// strdup
ptr2 = malloc(strlen(ptr1)+1);
strcpy(ptr2,ptr1);
```
* 用法
```clike=
char *p1 = "LOL";
char *p2;
p2 = strdup(p1);
printf("Duplicated string is : %s", p2);
```
* `queue_t*` 內的 head 指向 一個 queue 的開頭，queue 可分爲兩種 case
* `queue_t* X = NULL;` 即爲Null queue
* `queue_t* X = ...;`<br> `X->head = NULL;` 則是 Empty queue
* 7.Programming Task
* **q_new**: Create a new, empty queue.
* **q_free**: Free all storage used by a queue.
* **q_insert_head**: Attempt to insert a new element at the head of the queue (LIFO discipline).
* **q_insert_tail**: Attempt to insert a new element at the tail of the queue (FIFO * discipline).
* **q_remove_head**: Attempt to remove the element at the head of the queue.
* **q_size**: Compute the number of elements in the queue.
* **q_reverse**: Reorder the list so that the queue elements are reversed in order. This function should not allocate or free any list elements (either directly or via calls to other functions that allocate or free list elements.) Instead, it should rearrange the existing elements.
這段有說使用到 string 的時候，必須 **create and store a copy of the string by calling `malloc` to allocate space**, 還有 **allocate space for each string based on its length.**
`q_insert_tail` 和 `q_size` 要達到 $O(1)$
## 實作
這裏是實作的過程，一個 function 接上 一個 function 做解釋，並且優先解釋先完成的 function。
* `queue.h`
* 首先更改原本 queue 的 struct 結構，增加一個只想 tail 的 pointer 和 節點數計算
```clike=
typedef struct {
list_ele_t *head;
list_ele_t *tail;
long long int list_count;
} queue_t;
```
這樣的話`q_size` 和 `q_insert_tail` 就都能夠有辦法實現 $O(1)$ 的演算法
* `q_new`
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q == NULL) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->list_count = 0;
return q;
}
```
* 起始化 queue 結構，根據作業定義 `q->head = NULL;` 即表示這是一個空 queue
* `q_insert_head`
```clike=
bool q_insert_head(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
strcpy(newh->value, s);
if (q->list_count == 0) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
q->list_count++;
return true;
}
```
* 根據作業要求進行一下判定 和 宣告流程
* 判斷argument 的 q 是否爲NULL，若是則回傳 false
* 嘗試建立新節點 `list_ele_t *newh;`，若`malloc`過程失敗則回傳 false
* 接下來進行字串copy 的動作
這裏有一個疑問，本來的寫法是 `newh->value = strdup(s);`，但是這樣的話執行 `qtest` 會回傳 **attempted to free unallocated space error**，因此參考了 **`strdup`** 的實作
```clike=
newh->value = malloc(strlen(s) + 1);
strcpy(newh->value, s);
```
:::warning
問：爲什麼strdup 不行？
已解決
因爲這支程式裏面呼叫的 `malloc` 不是系統的 `malloc` 而是 `qtest`的，因此如果用 `strdup` （`qtest` 沒有提供）雖然可以過掉測資，但是因爲我的程式碼裏面有顧慮到 `free` 每一個節點的時候先 `free` 掉 `value`，但是若使用`strdup` 所 `malloc` 出來的空間 `qtest` 是不知情的！這就造成了 `qtest` 顯示 attempted to free unallocated space error。
`qtest`的程式碼有自行模擬`malloc`
:::
然後一樣嘗試在`malloc` 的過後判斷 `value` 是 `NULL` 的話回傳false
:::warning
因爲qtest 內有一個選項是可以開啓 malloc 成功率，當不爲0 的時候，就會有很多情況回傳NULL
因此若`newh->value == NULL` 則必須同時兼顧`newh` 的`free` 的動作，不然會有memory leak 的錯誤
:::
* 判斷list_count 是否爲0，若爲0 則先讓 `tail` 指向 `newh`
* 讓`newh->next = q->head` （`head` 可能爲 NULL，即創立第一個節點）
* 讓`q->head = newh` （更新 `head` pointer 指向新節點）
* `list_count++` 增加節點數量
* `q_insert_tail`
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
if (q == NULL) {
return false;
}
list_ele_t *newh;
newh = (list_ele_t *) malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
}
newh->value = malloc(strlen(s) + 1);
if (newh->value == NULL) {
free(newh);
return false;
}
strcpy(newh->value, s);
if (q->list_count == 0) {
q->head = newh;
} else {
q->tail->next = newh;
}
newh->next = NULL;
q->tail = newh;
q->list_count++;
return true;
}
```
* 基本上與`q_insert_head`的實作方式一樣
* `list_count` 爲0 的時候，讓`head`指向新的節點，若不是0 則 `tail->next = newh`
* 新節點的next 指向 NULL
* `tail` 指向新節點
* `list_count++` 增加節點數量
* `q_remove_head`
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q == NULL || q->head == NULL) {
return false;
}
if (sp != NULL) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *temp = q->head;
q->head = q->head->next;
free(temp->value);
free(temp);
q->list_count--;
return true;
}
```
* 根據作業要求
* 若`q` 與 `q->head` 爲 NULL 則回傳 false
* 若 `sp` 非 NULL，則把移除的節點的字串複製進去，sp 可以接受的最大size 爲 `bufsize - 1` 因此要寫好條件判定式，而且 array 最後需要以 NULL terminator 結束（`s[bufsize - 1]`）
* 使用 `strncpy` 複製 給定大小的字串長度
* 建立一個名爲 `temp` 的pointer 指向 `head` 節點
* 把 `head` 指向 `head->next`
* 把 `temp` 所佔的空間 free 掉
* `list_count++` 節點數量減一
* * 10/01 更新，減少不必要的程式碼
* `q_size`
```clike=
int q_size(queue_t *q)
{
if (q == NULL || q->head == NULL) {
return 0;
}
return q->list_count;
}
```
* 若 `q` 是 NULL 或者 empty 的話回傳0，否則回傳queue 長度
* `q_reverse`
```clike=
void q_reverse(queue_t *q)
{
if (q != NULL && q->head != NULL && q->head->next != NULL) {
list_ele_t *itr = q->head->next;
list_ele_t *temp;
q->tail = q->head;
while (itr != NULL) {
temp = itr->next;
itr->next = q->head;
q->head = itr;
itr = temp;
}
q->tail->next = NULL;
}
}
```
* 根據作業要求
* 若`q` 與 `q->head` 爲 NULL 則 NO EFFECT
* 不能呼叫其他函式
* 把`q->tail` 指向 `q->head` ，從第二個節點開始每一個節點指向上一個節點，結束後讓 `q->head` 指向 最後一個節點
* 實作方式可看程式碼
* 10/01 更新，減少使用的迴圈變數
* `q_free`
```clike=
void q_free(queue_t *q)
{
if (q != NULL) {
list_ele_t *itr = q->head;
while (q->head != NULL) {
itr = q->head;
if (q->head->value != NULL) {
free(q->head->value);
}
q->head = q->head->next;
free(itr);
}
free(q);
}
}
```
* 根據作業要求進行撰寫
* 留意作業要求並沒有註明這個 function 需要在 `q == NULL` 的時候回傳什麼值，但是有一筆測資內含指令 `free` ，而 qtest 結束的時候也會進行 `free` 指令的動作，因此進行了兩次`free`，若不檢查`q` 的狀態的話會出錯(double free error)
* 先 `free` 字串的空間，再 `free` 掉節點所佔的空間
## 程式執行結果
```
$ make test
```
截圖
```
scripts/driver.py
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
--- trace-01-ops 6/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
--- trace-05-ops 6/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
--- trace-06-string 7/7
+++ TESTING trace trace-07-robust:
# Test operations on NULL queue
--- trace-07-robust 7/7
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 7/7
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 7/7
+++ TESTING trace trace-10-malloc:
# Test of malloc failure on new
--- trace-10-malloc 7/7
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 7/7
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 7/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
--- trace-13-perf 7/7
+++ TESTING trace trace-14-perf:
# Test performance of size
--- trace-14-perf 7/7
+++ TESTING trace trace-15-perf:
# Test performance of insert_tail, size, and reverse
--- trace-15-perf 7/7
--- TOTAL 100/100
```
Sign in with Wallet
Connect another wallet