# 2019q3(Homework2) Lab0
contributed by <` hankchang805`>
#### tags: `sysprog2019`
## 閱讀資料
* [C Programming lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
* [F01: lab0](https://hackmd.io/s/BJA8EgFB4)
## 作業要求
* 用 linked-list 來實作 queue
* queue 要支援 LIFO(Last in,First out) 及 FIFO(Fist in,First out)
## 開發環境
* Operating System : `Ubuntu 18.04 64bit Amd64版本`
* Compiler : `gcc 8.1.0 `
## 測試結果
:::danger
文字訊息==不要==用圖片展現
:notes: jserv
:::
* 100分的狀態但相信仍存在效能改善的潛力
:::danger
純粹是目前的評分程式太保守，之後改版會加上更多限制
:notes: jserv
:::
## 實作記錄
### ` queue.h`
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail; /* add tail pointer in the queue */
int size;
} queue_t;
```
* 新增` list_ele_t *tail` 去指向尾端的元素
* 新增 ` int size` 來記錄目前 queue 的大小
:::danger
注意偏好的程式碼縮排: 4 個空白字元，K&R 風格，在 HackMD 的程式碼列表也該如此
:notes: jserv
:::
### `q_new`
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q) {
printf("Fail to new Queue\n");
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
* 這邊一開始先讓 `q->head` 及 `q->tail` 的值都是 `NULL`
### `q_free`
```cpp
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
if (!q)
return;
list_ele_t *ptr = NULL;
while (q->head) {
ptr = q->head;
q->head = q->head->next;
free(ptr->value);
free(ptr);
}
free(q);
}
```
* 只用 `ptr` 指標指到要刪除的元素，要完整刪除該元素必須連同 `ptr->value` 一起，不然會造成 `ptr->value` 那一塊記憶體刪除不了
* `free(q)` 把 queue 的記憶體空間釋放掉
### `q_insert_head`
```clike
bool q_insert_head(queue_t *q, char *s)
{
// printf("%p\n",(void*)s);//used to debug
if (!q)
return false;
list_ele_t *newh;
newh = malloc(sizeof(list_ele_t));
if (!newh) {
printf("Allocate fail!!\n");
return false;
}
char *in = malloc((strlen(s) + 1) * sizeof(char));
if (!in) {
free(newh);
return false;
}
strcpy(in, s);
newh->value = in;
newh->next = q->head;
if (!q->tail)
q->tail = newh;
q->head = newh;
q->size++;
return true;
}
```
* 要幫新增的 `value` 要一塊記憶體空間不然傳進來的 `argv` 指向的都是同個記憶體位址，若不分派一塊記憶體空間會使得後面插進來的元素改動了前面已存在的元素值
* 如果 `q->tail` 是 `NULL` ， 代表這次執行插入是第一次，讓 `q->tail` 指向剛剛插入的元素往後的操作才不會造成 queue 的 list 斷掉
### `q_inset_tail`
```clike
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)
return false;
list_ele_t *newt;
newt = malloc(sizeof(list_ele_t));
if (!newt) {
printf("Allocate fail!!\n");
return false;
}
char *in = malloc((strlen(s) + 1) * sizeof(char)); //+1 is a point
if (!in) {
free(newt);
return false;
}
strcpy(in, s);
newt->value = in;
newt->next = NULL;
if (!q->tail && !q->head) {
q->tail = newt;
q->head = newt;
} else {
if (!q->tail) {
q->tail = newt;
} else {
q->tail->next = newt;
q->tail = newt;
}
}
q->size++;
return true;
}
```
* 大致上跟 ` q_insert_head` 相同 ， 每次執行後 `q->tail` 要向後一個才會指向最後一個值
* 如果 `q->head` 是 `NULL` ，讓 `q->head` 指向剛剛插入的元素；防止 queue 斷掉
### `q_remove_head`
```clike
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (!q)
return false;
list_ele_t *rm = NULL; // do not malloc for rm ptr , it will cause a block
// can't re removed
// char *temp = malloc((strlen(q->head->value)+1) * sizeof(char));
if (!q->head)
return false;
rm = q->head;
if (sp) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
q->head = q->head->next;
free(rm->value);
free(rm);
q->size--;
return true;
}
```
* `sp` 不是 `NULL` 代表要執行 `rh` 指令， 要回報刪除的值是什麼；因此，要複製 `q->head` 的內容到 `sp` 中
* `sp` 是`NULL` 代表要執行 `rhq` 指令， 不用回報刪除的值是什麼只要做單純的刪除就行了
### `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)
return 0;
return q->size;
}
```
* 回傳 `q->size` 的值
### `q_reverse`
```clike
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (!q)
return;
list_ele_t *pre;
list_ele_t *middle;
list_ele_t *last;
pre = q->head;
middle = NULL;
last = NULL;
while (pre) {
last = middle;
middle = pre;
pre = pre->next;
middle->next = last;
}
q->tail = q->head;
q->head = middle;
}
```
* 使用三個指標來輔助反轉操作，每次都將 `middle->next` 指向 `pre` 所指的 `element` ，如此一來可以讓 list 的方向反過來；最後把 `q->tail` 及 `q->head` 調換就可以完成 `q_reverse` 操作
* 第六感認為還不是最好的作法，使用的輔助指標多；會再思考有沒有辦法用少一點指標
## 嘗試回答qtest裡的行為與技巧
### `Signal handler`
qtest 內的 signal 出現在 `queue_init()` 中
```clike
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
一開始以為 `signal()` 是定在另外幾個 header 檔裡，所以不斷地尋找都無下文才意識到是 C Library 裡面的東西，於是打開 C99 規格書翻找在第427頁 B.13 Signal handling <signal.h> 有以下內容：
* ` void ( *signal(int sig, void (*handler)(int)) ) (int) ` signal 函式宣告下面這篇有講解如何解讀它
* [How to read this prototype?](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype)
:::danger
摘錄原文並解釋，特別是比較 C99 列出的 signal 和 POSIX signal 數量的差異，思考當初 C 語言規格制定者如何針對 portability 去設想
:notes: jserv
:::
裡面的 sig 參數看起來很熟悉，於是去 [linux manual](http://man7.org/linux/man-pages/man7/signal.7.html) 找一下看到了好多 signal number 以及它所代表的意義：
* ` SIGSEGV`: Invalid memory reference
* ` SIGALRM`: Timer signal from alarm(2)
對於這段程式的理解：
* SIGSEGV 是處理 segmentation fault 的，一旦程式在執行時產生 segmentation fault 的問題會透過 signal() 這個函式帶入 SIGSEGV 及 sigsegvhandler 兩個參數產生 exception 的呼叫，請作業系統來處理
:::danger
「產生 segmentation fault 的問題」這句話有誤，請回頭看 page fault handler 的運作機制，再用精準的話語描述
:notes: jserv
:::
* SIGALRM 為處理 Alarm Clock ， 藉由 alarm(time) 去設定每幾秒鐘後產生 SIGALRM 的信號，而 alarm(0) 則會取消當前 Timer 的處理
* 在 `qtest.c` 中對於 queue 的操作開始跟結束可以見到 `exception_setup(true)` 及 `exception_cancel()` 這兩個 function 如下：
```clike
if (exception_setup(true))
rval = q_remove_head(q, NULL, 0);
exception_cancel();
```
這部分看起來是在準備對 queue 進行操作之前先設定 Alarm Clock 的值是 1 (true) ，如果超過 1 秒沒有進到 exception_cancel() 則會發出 SIGALRM 信號來終止掉這個行程 (process) 以防止無限迴圈發生
:::danger
避免說「看起來」，你可以做實驗來確認
:notes: jserv
:::
## 參考資料
* [你所不知道的 C 語言: 指標篇](https://hackmd.io/@sysprog/HyBPr9WGl)
* [afcidk 的開發紀錄](https://hackmd.io/@afcidk/ry4VZS9SN)
Sign in with Wallet
Connect another wallet