# 2019q3 Homework2 (lab0)
contributed by < `Ting199708` >
## 開發環境
作業系統：Ubuntu 18.04.2 LTS
## 實作
完成此 lab 我總共修改了兩個檔案 `queue.h` 及 `queue.c` ，下面將分別分析我所變更的地方
### queue.h
在此檔案中我修改了 queue_t 的 struct ，以便在實作 ==q_size== 及 ==q_insert_tail== 時更加方便並增加效率。
程式碼如下：
```cpp
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
* tail : 可以提高在進行 q_insert_tail 時的效率，直接存取 queue 的 tail。
* size: 透過新增一個 size 變數，便可在 insert 及 remove 的同時變更 size ，如此在呼叫 q_size function 時可以直接回傳。
### queue.c
以下就各 function 分別解釋
---
#### q_new
程式碼：
```cpp
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
q->head = NULL;
q->tail = NULL;
q->size = 0;
return q;
}
```
此部分主要將在 headfile 中新增的資料結構進行初始化，並且處理 malloc 回傳 ==NULL== 的情況。
#### q_insert_head
程式碼：
```c
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if(q == NULL || s == NULL) return false;
newh = malloc(sizeof(list_ele_t));
if(newh == NULL) return false;
char *value = malloc(strlen(s) * sizeof(char) + 1);
if(value == NULL) {
free(newh);
return false;
}
strcpy(value, s);
//Insert the value into newh
newh->value = value;
if (q->size == 0) q->tail = newh;
newh->next = q->head;
q->head = newh;
q->size++;
return true;
}
```
這邊新增了 `queue` 及 `s` 為 NULL 時對應的處理，另外，除了更新 `q->head` 外，因為新增了 `q->tail` ，因此若 `q->size` 為 0 時同時也要更新 `q->tail` 的參數，並且也要將 `q->size` 加一。
#### q_insert_tail
程式碼：
```c
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 */
list_ele_t *newt;
if(q == NULL || s == NULL) return false;
newt = malloc(sizeof(list_ele_t));
if(newt == NULL) return false;
char *value = malloc(strlen(s) * sizeof(char) + 1);
if(value == NULL) {
free(newt);
return false;
}
strcpy(value, s);
newt->value = value;
newt->next = NULL;
if(q->size != 0) q->tail->next = newt;
else q->head = newt;
q->tail = newt;
q->size++;
return true;
}
```
這邊執行的動作跟 q_insert_head 大同小異，如同上方所述，除了更新 `q->tail` 的參數外，若 `q->size` 為 0 時， `q->head` 同時也要進行更新。
#### q_free
程式碼：
```c
void q_free(queue_t *q)
{
if (q == NULL)
return;
list_ele_t *temp = NULL;
while (q->head != NULL) {
temp = q->head;
q->head = temp->next;
free(temp->value);
free(temp);
}
free(q);
}
```
這邊透過了一個 while 迴圈來對 queue 內的 elements and strings 進行 free 的動作，這邊我在開發時碰到最大的問題就是 while 無窮迴圈的錯誤，後來發現是在 `q_insert_head` 及 `q_insert_tail` 時在 malloc value 時需要加 1 來儲存結尾的 '\0' 字元。
#### q_remove_head
程式碼：
```c
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if(q == NULL || sp == NULL) return false;
if(q->size == 0) return false;
//sp = malloc(bufsize * sizeof(char));
if(sp != NULL && bufsize > 0) {
strncpy(sp, q->head->value, bufsize-1);
sp[bufsize-1] = '\0';
}
list_ele_t *temp;
temp = q->head;
q->head = temp->next;
free(temp->value);
free(temp);
q->size--;
return true;
}
```
根據題目要求，除了將 head 移除外，若 ==sp != NULL== 則要將 rempve item 複製至 sp 內，且長度為 `bufsize` ，因此我對 sp 進行判斷是否為 NULL ，再透過 `strncpy` 函式來將 remove item 複製 `bufsize-1` 的長度進入 sp 。
#### q_size
程式碼：
```c
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
程式碼：
```c
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if(q == NULL) return;
if(q->size == 0) return;
list_ele_t *temp1 = NULL;
list_ele_t *temp2 = q->head;
list_ele_t *temp3 = q->head->next;
while(temp3 != NULL) {
temp3 = temp2->next;
temp2->next = temp1;
temp1 = temp2;
temp2 = temp3;
}
temp1 = q->head;
q->head = q->tail;
q->tail = temp1;
}
```
這邊我透過的技巧為將 queue 內部各參數的 `next` 值進行反向的動作，再將 `q->head` 與 `q->tail` 進行交換，如下圖：
## qtest分析
### Signal Handler
在 `qtest.c` 中，我找到了以下程式碼：
```c
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
函數定義如下：
```c
void (*signal(int sig, void (*func)(int)))(int)
```
<s>通過上網搜尋</s>， signal 函數可以收集由 os 所發出的信號進行對應的處理，他可以處理的信號碼如下表：
:::danger
避免說「上網搜尋」，明確將規格書和第一手材料列出！
:notes: jserv
:::
| 信號碼 | 意義 |
| -------- | -------- |
| SIGABRT | Signal Abort: 程式異常中止 |
| SIGFPE | Signal Floating-Point Exception: 算術運算錯誤 |
| SIGILL | Signal Illegal Instruction: 非法函數 |
| SIGINT | Signal Interrupt: 中斷信號，通常由用戶生成，如 ctrl-C |
| SIGSEGV | Signal Segmentation Violation: 非法訪問內存 |
| SIGTERM | Signal Terminate: 程式中止請求信號 |
## 時間複雜度實驗
參考並利用 afcidk 同學所編寫的 `qtest-t` 來對我的程式進行時間複雜度的實驗，執行結果如下：
:::danger
需要解釋原理和分析限制
:notes: jserv
:::
```
Note1: Since we use statictic method to test if the function has constant
time complexity, sometimes it requires larger time to show that it
REALLY IS POLYNOMINAL time, however, you can tell instinctively that
it is not constant time if the calculating process is too slow. :)
(normally, the change of "max t" field should be really fast)
Note2: You should pass the original time limit (1 sec) first!
Testing insert_tail... Press Ctrl-C to enter next mode
meas: 1.09 M, max t: +0.67, max tau: 6.37e-04, (5/tau)^2: 6.17e+07. For the moment, maybe constant time.
^C
Testing q_size...... press Ctrl-C to leave.
meas: 13.20 M, max t: +0.53, max tau: 1.47e-04, (5/tau)^2: 1.16e+09. For the moment, maybe constant time.
```
可見， `q_insert_tail` 及 `q_size` 皆為 O(1) 時間複雜度
## Reference
* [Signals in C language](https://wiki.jikexueyuan.com/project/c/signal.html)
* [afcidk同學的共筆](https://hackmd.io/@afcidk/ry4VZS9SN?type=view)
Sign in with Wallet
Connect another wallet