owned this note
owned this note
Published
Linked with GitHub
# 2018q3 Homework2
contributed by <`jesus255221`>
>請補上實驗環境
>[name=課程助教][color=red]
>
## 實驗環境
```
OS: Linux Ubuntu 18.04 64位元
CPU: Intel E3 1230V2
MEM: 20GB DDR3
```
## 關於常數時間的考慮
``` clike=
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
*/
int q_size; //The size of q
list_ele_t *tail; //The tail of q
} queue_t;
```
作業要求必須要常數時間完成 size 的存取與 tail 的插入。很直覺的就是用空間換取時間。即
``` clike=
int q_size; //The size of q
list_ele_t *tail; //The tail of q
```
## ```malloc```失敗的考慮
以下節錄自 linux man page
> The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().
也就是說當 malloc 失敗時，將會回傳```NULL```。
程式碼裡面也多處檢查是否為 NULL pointer，這便是巨集使用的好時機。
```clike=
#define NULL_CHECK(condition) \
if (!condition) { \
return false; \
}
```
只要當```condition```為```NULL```時，便會回傳false。可用於會回傳```bool```型態的函數。
## q_new
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q) {
return NULL;
}
q->head = NULL;
q->tail = NULL;
q->q_size = 0;
return q;
}
```
一開始先做```malloc```檢查，成功以後將 ```head, tail, q_size```初始化。
## q_free
``` clike=
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
if(!q){
return;
}
/* Free queue structure */
list_ele_t *current_ptr = q->head, *prev;
while (current_ptr != NULL) {
free(current_ptr->value); // Free the current string
prev = current_ptr; // Save the previous list node
current_ptr = current_ptr->next; // Go to the next node
free(prev); // free the previous node
};
free(q);
}
```
一樣先檢查```q```是否為```NULL```，再處理記憶體釋放。
創建兩個指標用於走訪 list
直到目前指標等於```NULL```時再停下，不然就持續走訪每個節點。
釋放字串所用的空間之後把目前 pointer 指到下個節點，再把上個節點的空間釋放。
## q_reverse
```clike=
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (!q) {
return;
}
list_ele_t *prev = NULL, *current = q->head, *next;
while (current) {
next = current->next; // Point to the next node
current->next = prev; // Point the next pointer of current pointer to the previous one
prev = current; // Point the previous pointer to the current pointer
current = next; // Point the current pointer to the next pointer
}
current = q->head; // Reverse the head and tail
q->head = q->tail;
q->tail = current;
return;
}
```
一樣先檢查```q```是否為```NULL```。準備三個指標，```*prev, *current, *next```，當目前的指標不是```NULL```時，把目前指標的 next 指向上一個 node。如此直到 current pointer 為```NULL``` 為止。最後再 exchange head and tail
## q_insert_head, q_insert_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 */
list_ele_t *newt;
NULL_CHECK(q);
newt = malloc(sizeof(list_ele_t));
NULL_CHECK(newt);
newt->value = malloc(strlen(s) + 1);
if (!newt->value) {
free(newt);
return false;
}
strcpy(newt->value, s);
newt->value[strlen(s)] = '\0';
newt->next = NULL;
// If this node is the first node
if (!q->q_size) {
q->head = newt;
} else {
q->tail->next = newt;
}
q->tail = newt;
q->q_size++;
return true;
}
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
/* What should you do if the q is NULL? */
NULL_CHECK(q);
newh = malloc(sizeof(list_ele_t));
NULL_CHECK(newh);
/* Don't forget to allocate space for the string and copy it */
// malloc string size plus the terminating character
newh->value = malloc(strlen(s) + 1);
/* What if either call to malloc returns NULL? */
/* If malloc failed... */
if (!newh->value) {
free(newh);
return false;
}
// Copy the string
strcpy(newh->value, s);
newh->value[strlen(s)] = '\0';
/* If this is the first node in the list, set the tail to it*/
if (!q->q_size) {
q->tail = newh;
}
newh->next = q->head;
q->head = newh;
q->q_size++;
return true;
}
```
```q_insert_head``` 與 ```q_insert_tail``` 的實作非常類似。一開始先檢查 ```q``` 是否為 ```NULL```，之後再```malloc```新的記憶體給新的節點並且檢查是否成功。確認成功之後再配置節點內字串所需記憶體，再利用系統函數```strcpy```來複製字串，最後再將節點插入 queue 中並且進行相對應的節點更動。
## q_remove_head
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
NULL_CHECK(q);
NULL_CHECK(q->head);
if (sp) {
if (strlen(q->head->value) >= (bufsize - 1)) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
} else {
strncpy(sp, q->head->value, strlen(q->head->value));
sp[strlen(q->head->value)] = '\0';
}
}
free(q->head->value);
list_ele_t *head;
head = q->head;
q->head = q->head->next;
q->q_size--;
if (!q->q_size) {
q->tail = NULL;
}
free(head);
return true;
}
```
```q_remove_head```應該算是裡面比較複雜的函數了，一開始必須檢查是否是 quiet removal，也就是```sp```是否為```NULL```，之後再判斷真正字串的長度是否有比```bufsize```大。是，則複製 bufsize - 1 的字串(因為最後面要放```'\0'```)。否，則複製字串長度的資料就好。
之後再依序把節點的字串記憶體空間釋放，節點本身釋放；最後再更動```head```即可。如果此節點為 queue 的最後一個節點，則把```tail```也指向```NULL```。
### 至此， queue 已經可以通過```make test```
### 剩下就是研究到底如何實現 command line system
---
## qtest
qtest 裡面用到非常多```static```變數。但是```static```變數的生命週期能跨越檔案嗎？根據C99規格書 6.2.4.3 ```static```
> Its lifetime is the entire execution of the program and its stored value is initialized only once, prior to program startup.
>
原來是整個執行時期阿，那我就放心了。
### ```do_new```
```clike=
bool do_new(int argc, char *argv[])
{
if (argc != 1) {
report(1, "%s takes no arguments", argv[0]);
return false;
}
bool ok = true;
if (q != NULL) {
report(3, "Freeing old queue");
ok = do_free(argc, argv);
}
error_check();
if (exception_setup(true))
q = q_new();
exception_cancel();
qcnt = 0;
show_queue(3);
return ok && !error_check();
}
```
### ```report```
``` clike=
void report(int level, char *fmt, ...)
{
va_list ap;
if (!verbfile)
init_files(stdout, stdout);
//Output all the error message to the screen
if (level <= verblevel) {
va_start(ap, fmt);
vfprintf(verbfile, fmt, ap);
fprintf(verbfile, "\n");
fflush(verbfile);
va_end(ap);
if (logfile) {
va_start(ap, fmt);
vfprintf(logfile, fmt, ap);
fprintf(logfile, "\n");
fflush(logfile);
va_end(ap);
}
}
}
```
report 有一個很有趣的地方，參數輸入是```...```，也就是不定長度的傳入參數。關於這點C99在7.15有詳細的定義，先要用一個```va_list```來接住所有的參數，再來用```va_start```等來存取。如果有 logfile 則寫入。
### ```exception```
```clike=
bool exception_setup(bool limit_time)
{
if (sigsetjmp(env, 1)) {
/* Got here from longjmp */
jmp_ready = false;
if (time_limited) {
alarm(0);
time_limited = false;
}
if (error_message) {
report_event(MSG_ERROR, error_message);
}
error_message = "";
return false;
} else {
/* Got here from initial call */
jmp_ready = true;
if (limit_time) {
alarm(time_limit);
time_limited = true;
}
return true;
}
}
```
``` clike
void trigger_exception(char *msg)
{
error_occurred = true;
error_message = msg;
if (jmp_ready)
siglongjmp(env, 1);
else
exit(1);
}
```
這兩個函數也是很有趣，一開始```exception_setup```被呼叫時，會先設定```sigsetjmp```的細節把諸如 stack pointer 儲存起來，之後如果```trigger_exception```被呼叫時，```siglongjmp```便會被呼叫進而進入```exception_setup``` if 的上半部。
```clike=
/* Signal handlers */
void sigsegvhandler(int sig)
{
trigger_exception(
"Segmentation fault occurred. You dereferenced a NULL or invalid "
"pointer");
}
void sigalrmhandler(int sig)
{
trigger_exception(
"Time limit exceeded. Either you are in an infinite loop, or your "
"code is too inefficient");
}
static void queue_init()
{
fail_count = 0;
q = NULL;
signal(SIGSEGV, sigsegvhandler);
signal(SIGALRM, sigalrmhandler);
}
```
接下來在利用 ```signal``` 系統呼叫來設定```trigger_exception```的條件，這樣便可以做到外部 exception handling 的功能。真是博大精深
### ```do_remove_head```
```do_remove_head``` 比較複雜，以下分析將會利用註解來呈現（因為真的太長了阿阿阿）
```clike=
bool do_remove_head(int argc, char *argv[])
{
if (argc != 1 && argc != 2) {// 檢查參數個數是否合乎規定
report(1, "%s needs 0-1 arguments", argv[0]);
return false;
}
char *removes = malloc(string_length + STRINGPAD + 1);
if (removes == NULL) { // 這裡移除用字串除了原本的 string_length 還多加了
// padding 來檢查 memory leak
report(1,
"INTERNAL ERROR. Could not allocate space for removed strings");
return false;
}
char *checks = malloc(string_length + 1);
if (checks == NULL) {// 檢查命令列所輸入的字串是否 malloc 成功
report(1,
"INTERNAL ERROR. Could not allocate space for removed strings");
free(removes);
return false;
}
bool check = argc > 1;
bool ok = true;
if (check) {// 複製命令列所傳入之字串
strncpy(checks, argv[1], string_length + 1);
checks[string_length] = '\0';
}
removes[0] = '\0';//把 removes 第一個元素設為'\0'達到類似空字串的效果
memset(removes + 1, 'X', string_length + STRINGPAD - 1);//把剩下的byte全部設成'X'
removes[string_length + STRINGPAD] = '\0';//把最後一個byte設為'/0'
//所以事實上 removes 有兩個 '\0'
if (q == NULL) //做傳入 queue 檢查
report(3, "Warning: Calling remove head on null queue");
else if (q->head == NULL)
report(3, "Warning: Calling remove head on empty queue");
error_check();
bool rval = false;
if (exception_setup(true))// 開始上面的 outside exception handling
rval = q_remove_head(q, removes, string_length + 1);
exception_cancel();
if (rval) {
removes[string_length + STRINGPAD] = '\0';
if (removes[0] == '\0') {//檢查是否有存到剛剛移除的字串
report(1, "ERROR: Failed to store removed value");
ok = false;
} else if (removes[string_length + 1] != 'X') {
// 檢查移除字串最後是否為'X'（應為'\0'），memory 是否有洩漏
report(1,
"ERROR: copying of string in remove_head overflowed "
"destination buffer.");
ok = false;
} else {
report(2, "Removed %s from queue", removes);
}
qcnt--;
} else {// 如果剛剛的 rh 回傳失敗則執行以下
fail_count++;
if (!check && fail_count < fail_limit) {
report(2, "Removal from queue failed");
} else {
report(1, "ERROR: Removal from queue failed (%d failures total)",
fail_count);
ok = false;
}
}
if (ok && check && strcmp(removes, checks) != 0) {
// 比較移除字串和命令列所輸入字串是否相同。
report(1, "ERROR: Removed value %s != expected value %s", removes,
checks);
ok = false;
}
show_queue(3);
free(removes);
free(checks);
return ok && !error_check();
}
```
Sign in with Wallet
