# 2018q3 Homework2
contributed by <`jesus255221`>
>請補上實驗環境
>[name=課程助教][color=red]
>

## 實驗環境

OS: Linux Ubuntu 18.04 64位元
CPU: Intel E3 1230V2
MEM: 20GB DDR3

## 關於常數時間的考慮

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 的插入。很直覺的就是用空間換取時間。即

    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，這便是巨集使用的好時機。

#define NULL_CHECK(condition) \
    if (!condition) {         \
        return false;         \
    }

只要當```condition```為```NULL```時，便會回傳false。可用於會回傳```bool```型態的函數。

## q_new

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

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

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

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_remove_head

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;
}

之後再依序把節點的字串記憶體空間釋放，節點本身釋放；最後再更動```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```

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```

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```

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;
    }
}

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 的上半部。

/* 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```

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();
}