# 2019q3 Homework2 (lab0)
contributed by < `Benny1117Yen` >
#### tags: `sysprog2019`
:::danger
注意看作業要求，對於共筆格式有諸多規範。從細節小處做起！
:notes: jserv
:::
* [C Programming lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 作業目標
CMU [Introduction to Computer Systems (ICS)](http://www.cs.cmu.edu/~213/index.html) 準備了 [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf) 作為檢閱學生 C 語言程式設計的認知:
* 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.
實驗目標為實作 queue
* first in, first out (FIFO)
* last in, first out (LIFO)
## Resources
1. [C programming](https://en.wikibooks.org/wiki/C_Programming)
2. [Linked lists](http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/10-linkedlist.pdf)
* [我對Linked lists的筆記](https://hackmd.io/@P86071244/H1ReZsxur)
3. [Asympotic (big-Oh) notation](http://www.cs.cmu.edu/~iliano/courses/18S-CMU-CS122/handouts/05-sort.pdf)
4. [afcidk 的開發紀錄](https://hackmd.io/@afcidk/ry4VZS9SN)
5. [posutsai 的開發紀錄](https://hackmd.io/@posutsai/HkgKesMYX?type=view)
6. [你所不知道的 C 語言: 指標篇](https://hackmd.io/@sysprog/HyBPr9WGl)
## 實驗總覽
`queue.h` 這檔案含有以下結構宣告:
```cpp=
/* Linked list element */
typedef struct ELE {
char *value;
struct ELE *next;
} list_ele_t;
```
```cpp=
/* Queue structure */
typedef struct {
list_ele_t *head; /* Linked list of elements */
} queue_t;
```
如圖所示，將它們組合在一起以實現字符串駐列。駐列的上層表示形式是 `queue_t` 類型的結構。在開始代碼中，此結構僅包含單一個字段 `head`，之後需要變再添加其他字段。駐列內容表示為單鏈接列表，每個元素由類型為 `list_ele_t` 的結構表示，具有字段 `value` 和 `next`，分別存儲指向字符串的指針和指向下一個 `list元素` 的指針。最終列表元素的下一個指針設置為 `NULL`。您可以將其他字段添加到結構 `list_ele` 中，儘管不必這樣做。
* 圖1：駐列的鍊錶實現。每個列表元素都有一個 `value` 字段，該字段指向一個字符矩陣（C的字符串表示形式），`next` 字段指向下一個列表元素。字符根據 `ASCII` 編碼（以十六進制顯示）進行編碼。
回想一下，C 語言裡面字符串表示是型態為 `char` 的有值陣列。在大多數機器中，數據類型 `char` 表示為 `1 byte`。為了存儲長度為 `l` 的字符串，該陣列包含 `l + 1` 個元素，前一個 `l` 存儲字符的代碼（通常為 `ASCII1` 格式），最後一個設置為 `0`。列表元素的 `value` 字段是一個指針指到字符的陣列。該圖表示列表 `[“ cab”，“ bead”，“ cab”]` 的表示形式，其中字符 `a–e` 以十六進製表示為 `ASCII` 碼 `61–65`。 觀察字符串 `“cab”` 的兩個實例是如何由分離的陣列們來表示 -- 每個列表元素應具有其字符串的分離副本。
在我們的 `C` 代碼中，駐列是類型為 `queue_t *` 的指針。我們區分兩種特殊情況：`NULL` 駐列是指針值為 `NULL`。空駐列是指向有效結構，但是頭 (head) 字段的值為 `NULL`。所以代碼將需要正確處理這兩種情況，以及包含一個或多個元素的駐列。
## Programming Task
Your task is to modify the code in `queue.h` and `queue.c` to fully implement the following functions.
`q_new`: 創造新的空駐列。
`q_free`: 釋放駐列所佔用的記憶體。
`q_insert head`: 在駐列頭 (head) 加入 (insert) 新元素(以 LIFO 準則)。
`q_insert tail`: 在駐列尾 (tail) 加入 (insert) 新元素(以 FIFO 準則)。
`q_remove head`: 在駐列頭 (head) 去除 (remove) 元素。
`q_size`: 算出駐列中的元素量。
`q_reverse`: 以反向次序重新排列列表。這函數不該分配或釋放任何列表元素 (不論是直接地或呼叫其他有分配或釋放列表元素功能的函數。) 也就是說，它只能重排已經存在的元素。
在這兩個文件的註釋中可以找到更多詳細信息，包括如何處理無效的操作（例如，從空駐列或 `NULL` 駐列中刪除），以及函數應具有的副作用和返回值。
對於以字符串作為參數的函數，必須通過調用 `malloc` 分配空間（記住要包含終止字符的空間），然後從原始空間複製到新分配的空間，來創建和存儲字符串的副本。當需要釋放列表元素時，還必須釋放字符串使用的空間。不能假設字符串的長度有任何固定的上限 -- 必須根據字符串的長度為每個字符串分配空間。
其中兩個功能：`q_insert_tail` 和 `q_size` 將需要您付出一些努力才能達到所需的性能標準。原生執行將需要 `O（n）` 個步驟來處理具有 `n` 個元素的駐列。我們要求您的執行在時間 `O（1）` 內進行操作，即無論駐列大小如何，該操作僅需要固定數量的步驟。您可以藉由在 `queue_t` 數據結構中包括 (include) 其他字段並在插入，刪除和反轉列表元素時正確管理這些值來執行。
您的程序將在具有 `1,000,000` 個以上元素的駐列上進行測試。會發現無法使用遞歸函數在如此長的列表上進行操作，因為這將需要過多的堆棧 (stack) 空間。相反，需要使用循環 (loop) 遍歷 (traverse) 列表中的元素。
## 開發環境
:::danger
文字訊息 ==不要== 用圖片展現！
:notes: jserv
:::
## 實作記錄
### `queue.h`
依照內容中的註解需求，新增以下程式碼
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
/*
You will need to add more fields to this structure
to efficiently implement q_size and q_insert_tail
*/
list_ele_t *tail; /* Add tail pointer in the queue */
int size; /* Queue size */
} queue_t;
```
* 新增`list_ele_t *tail` 指向 `tail` 列表元素
* 新增 `int size` 為 queue 的大小
### `queue.c`
#### `queue_t *q_new()`
這是初始化的步驟
```cpp
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->size = 0;
return q;
}
```
* 創造一個頭、尾、大小都為 `NULL` 的駐列，若不能分配空間時，回傳 `NULL`。
#### `void q_free(queue_t *q)`
```cpp=
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
if (q == NULL)
return;
list_ele_t *ptr = q->head;
list_ele_t *ptr = NULL;
while (ptr) {
prev = ptr;
ptr = ptr->next;
free(prev->value);
free(prev);
}
/* Free queue structure */
free(q);
}
```
* if 條件是判斷駐列為 `NULL` 時，指針指到 `head`，指針的前一個位子為 `NULL`。
* while 是當 `ptr` 有值 (指到頭)，那麼 `prev` 就等於 `ptr` ，`ptr` 去指向 `next`。
* 如此，只用 `ptr` 指標就能指到要刪除的元素，要記得釋放指針指到的值記憶體大小跟指針本身記憶體大小。直到整個駐列清空。
* `free(q)` 釋放駐列所占記憶體大小。
#### `q_insert_head`
```cpp=
bool q_insert_head(queue_t *q, char *s)
{
/* What should you do if the q is NULL? */
if (q == NULL)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
/* Allocated failed */
if (newh == NULL)
return false;
/* Don't forget to allocate space for the string and copy it */
char *value = malloc((strlen(s) + 1) * sizeof(char));
if (value == NULL) {
free(newh);
return false;
}
strcpy(value, s);
newh->value = value;
/* What if either call to malloc returns NULL? */
newh->next = q->head;
if (q->size == 1)
q->tail = newh;
q->head = newh;
q->size++;
return true;
}
```
* 若駐列不為空，我們創造一新指針，並用 `malloc` 配置一個空間給它。
* 再用 `strcpy` 把值 copy 給 `value`，也就是新的駐列的記憶體位址。
* 而後新指針指向新的駐列頭，這裡有個判斷當 `size` 為 `1` 時，駐列尾指向新指針。
* 最後駐列大小加一。
#### `q_inset_tail`
```cpp=
bool q_insert_tail(queue_t *q, char *s)
{
/* You need to write the complete code for this function */
/* Remember: It should operate in O(1) time */
if (q == NULL)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
/* Allocated failed */
if (newt == NULL) {
return false;
}
char *value = malloc((strlen(s) + 1) * sizeof(char));
if (value == NULL) {
free(newt);
return false;
}
strcpy(value, s);
newh->value = value;
q->tail->next = newt;
q->tail = newt;
q->tail->next = NULL;
if (q->size == 1)
q->tail = newt;
q->head = newt;
q->size++;
return true;
}
```
* 跟 `q_insert_head` 概念相同，每次執行後 `q->tail` 要後移一個才會指向最後一個值。
### `q_remove_head`
```cpp=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (q == NULL || q->size == 0)
return false;
list_ele_t *tmp = q->head;
q->head = q->head->next;
int copy_len = bufsize / sizeof(char) - 1;
if (sp != NULL) {
memcpy(sp, tmp->value, copy_len);
sp[copy_len] = '\0';
}
free(tmp);
q->size--;
if (q->size == 0)
q->tail = NULL;
return true;
}
```
* 先用一個 tmp pointer 儲存原始 head 作為後來的 free 以及字串處理使用。
* 更新 q->head 並調整 size。
* 題目要求要複製 bufsize - 1 長度的字串到 sp ，並在字串最後補上節數字元 ‘\0’，我這裡使用的是 memcpy 而非 strdup，memcpy 的第三個參數，表示的是要拷貝的長度，所以我們必須先計算這樣的長度代表幾個 char 並在適當位置補上結束字元。
* 最後在針對 tmp 做釋放。
* 若是在移除 head 之後，list 內沒有任何節點，重複上述所有步驟，`q->head = q->head->next` 並不會受到影響因為會被更新為 NULL。由於現在 list 內沒有任一結點，所以我們也要把 tail 設為 NULL。
### `q_size`
```clike
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
if (q == NULL)
return 0;
return q->size;
}
```
### `q_reverse`
```clike
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (q == NULL)
return false;
list_ele_t *tmp = NULL;
prev = q->head;
while (prev) {
tmp = q->head;
q->head = q->head->next;
free(tmp->value);
free(tmp);
}
free(q);
}
```
## `qtest` 分數
```cpp=
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Freed queue, but 3 blocks are still allocated
--- trace-01-ops 0/6
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, and remove_head
ERROR: Removed value meerkat != expected value gerbil
ERROR: Removed value bear != expected value meerkat
ERROR: Removed value gerbil != expected value bear
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
ERROR: Removal from queue failed (1 failures total)
--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, reverse, and remove_head
ERROR: Removed value gerbil != expected value squirrel
ERROR: Removed value vulture != expected value gerbil
ERROR: Removed value bear != expected value gerbil
ERROR: Removed value gerbil != expected value bear
ERROR: Removed value squirrel != expected value dolphin
Error limit exceeded. Stopping command execution
--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, and size
ERROR: Freed queue, but 6 blocks are still allocated
--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head reverse, and size
ERROR: Removed value gerbil != expected value dolphin
ERROR: Removed value bear != expected value gerbil
ERROR: Removed value meerkat != expected value bear
ERROR: Removed value bear != expected value meerkat
ERROR: Segmentation fault occurred. You dereferenced a NULL or invalid pointer
ERROR: Removal from queue failed (1 failures total)
Error limit exceeded. Stopping command execution
--- trace-05-ops 0/6
+++ TESTING trace trace-06-string:
# Test of truncated strings
ERROR: Removed value aardvark_bear_dolphin_gerbil_jaguar != expected value meerkat_panda_squirrel_vulture_wolf
ERROR: Removed value aardvark_bear_dolphin_gerbil_j != expected value meerkat_panda_squirrel_vulture
ERROR: Removed value meerkat_panda_squirre != expected value aardvark_bear_dolphin
ERROR: Removed value meerkat_ != expected value aardvark
ERROR: Removed value meerkat_panda_squirrel_vulture_wolf != expected value aardvark_bear_dolphin_gerbil_jaguar
Error limit exceeded. Stopping command execution
--- trace-06-string 0/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
ERROR: Freed queue, but 1 blocks are still allocated
--- trace-09-robust 0/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
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-12-malloc 0/7
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-13-perf 0/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
ERROR: Freed queue, but 2 blocks are still allocated
--- trace-15-perf 0/7
--- TOTAL 35/100
```
* 分數還有待提高，這部份我還需要在修正。做單元測試有助於檢查函數可不可行，通常會以預期報錯或回傳正確來設計，當中也長用到 `Pseudo code`。
## `qtest` 技巧 -- signal handler
待補
## 解析 Valgrind 的運作原理和針對本程式的使用
待補
Sign in with Wallet
Connect another wallet