# 2020q3 Homework1 (lab0)
{%hackmd QnyEFBdERZebn4iQDXNPnA %}
contributed by < jeff14994 >

###### tags: `sysprog2020` `2020` `lab0` `hw1` `week1`
## 開發環境

#OS:
Linux 5.3.0-64-generic #58-Ubuntu SMP Fri Jul 10 19:33:51 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

#gcc version
gcc (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008

## 作業要求
1. q_new: 建立新的「空」佇列;
2. q_free: 釋放佇列所佔用的記憶體;
3. q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
4. q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
5. q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
6. q_size: 計算佇列中的元素數量。
7. q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
8. q_sort: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;
## 實作

### queue.h
首先，先在 queue.h 加入`dlist_ele_t *tail`，使得 Queue 有 tail 的元素。

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

### queue.c
按題目要求，若是一個空的 Queue，則回傳 NULL。第9行，用 if 來判斷 q 是否為空的 Queue。 第12行，另外利用 q->tail 增加 tail 的元素，並將其設定指向 NULL，目的是指向 Queue 的尾端。
1. q_new:

/*
 * Create empty queue.
 * Return NULL if could not allocate space.
 */
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;
}

若 Queue head 指標為空值，則無需檢查。若非空值，則遍歷整個 Queue 與其 linked list 將其刪除。q->head->next 將其指向下一個 link list 位址，若為空值則跳出迴圈

2. q_free:

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    
    /* Free queue structure */
    if (q == NULL)
        return;
    // if head exists, we keep on searching next 
    while (q->head) {
        // Update tmp
        list_ele_t *tmp = q->head;
        q->head = q->head->next;
        // freeing the strings
        free(tmp->value);
        // freeing the list elements 
        free(tmp);
    }
    free(q);
}

queue.h 裡有描述代辦事項：

3. q_insert_head:
- Attempt to insert element at tail of queue.
- Return true if successful.
- Return false if q is NULL or could not allocate space.
- Argument s points to the string to be stored.
- The function must explicitly allocate space and copy the string into it.

不像strcpy()，strncpy()不會向dest追加 '\0'，這會引起了很多不合常理的問题。因此若使用strcpy()，length 要再減一，因為strcpy() 會自動增加 '\0'

在 make test 的時候跳出這個警告：

Dangerous function detected in /home/jeff14994/Desktop/linux2020/week1/lab0-c/queue.c
76:    strcpy(newh->value, s);

Read 'Common vulnerabilities guide for C programmers' carefully.

https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml

因為 strcpy 不會檢查邊界，因此可能產生 Buffer over flow，有心人士可以藉此控制 EIP 暫存器，執行任意程式。

bool q_insert_head(queue_t *q, char *s)
{
    /* TODO: What should you do if the q is NULL? */
    /* What if either call to malloc returns NULL? */
    if (q == NULL) {
        return false;
    }

    // New head to be allocated memory
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL) {
        return false;
    }

    /* Don't forget to allocate space for the string and copy it */
    // Allocate space for string to checok
    int length = strlen(s) + 1;
    newh->value = malloc(sizeof(char) * (length));
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    // Copy from the source to the newly allocated space
    strcpy(newh->value, s);

    newh->next = q->head;
    // Move head in front of newh
    q->head = newh;
    // If No any element
    if (q->tail == NULL) {
        q->tail = newh;
    }
    // Queue size grows, thus plus one
    q->size++;
    return true;
}

4. q_insert_tail:
與 q_insert_head 大同小異，差異在第30行的判斷，判斷 Queue 是否為空？ 若是，則將新的 tail 加在 head 之後；若否，則將新的 tail 加在原本 tail 指標的下一個位址。透過第36行，將 q->tail 重新指向 link list 最後端。[備忘：忘記加了：tail = newt; 導致分數提不起來。]

bool q_insert_tail(queue_t *q, char *s)
{
    /* TODO: You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */
    if (q == NULL) {
        return false;
    }

    // New head to be allocated memory
    list_ele_t *newt;  // newt represents new tail
    newt = malloc(sizeof(list_ele_t));
    if (newt == NULL) {
        return false;
    }

    /* Don't forget to allocate space for the string and copy it */
    // Allocate space for string to checok
    int length = strlen(s) + 1;
    newt->value = malloc(sizeof(char) * (length));
    if (newt->value == NULL) {
        free(newt);
        return false;
    }
    // Copy from the source to the newly allocated space
    strncpy(newt->value, s, length);
    // Set this element to the last one
    newt->next = NULL;
    // See if the queue is empty or not. If yes, the head is the new tail, if
    // not, put the new tail in the next of the original tail
    if (q->size == 0) {
        q->head = newt;
    } else {
        q->tail->next = newt;
    }
    // Move q->tail to newt
    q->tail = newt;

    // Queue size grows, thus plus one
    q->size++;
    return true;
}

5. q_remove_head:
參考 dalaoqi 同學的做法，用 sprinrf() 複製字串。sprintf()用法：

int snprintf(char *str, size_t size, const char * restrict format, ...)

若 Queue 是 NULL 或空值， return false。若 sp 不等於 NULL ，則將字串複製到 sp。並且更新 q->head 到下一個位置、並釋放記憶體位置、並將 size 減一。

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* TODO: You need to fix up this code. */
    /* TODO: Remove the above comment when you are about to implement. */
    if (q == NULL || q->head == NULL) {
        return false;
    }
    list_ele_t *tmp = q->head;
    // If sp is not NULL copy the string to sp
    if (sp != NULL) {
        snprintf(sp, sizeof(bufsize), "%s", tmp->value);
    }
    // Update head to next node
    q->head = q->head->next;
    free(tmp->value);
    free(tmp);
    // Minus one in aize
    q->size--;
    return true;
}

6. q_size:
在 O(1)時間回傳queue的大小

int q_size(queue_t *q)
{
    if (q == NULL || q->head == NULL) {
        return 0;
    } else {
        return q->size;
    }
}

7. q_reverse:
參考 ZhuMon 的畫的流程圖，以實現程式碼。我將註解寫在程式碼當中

void q_reverse(queue_t *q)
{
    /* TODO: You need to write the code for this function */
    /* TODO: Remove the above comment when you are about to implement. */
    if (q == NULL || q->head == NULL) {
        return;
    }

    list_ele_t *curr = q->head;
    list_ele_t *prev = NULL;

    // See if q->head exists, if yes, than keep going
    while (q->head) {
        // get next node
        list_ele_t *next = q->head->next;
        // Change the head->next to previous node
        q->head->next = prev;

        // Update prev pointer
        prev = q->head;
        // Update q->head to next node
        q->head = next;
    }
    // Update head to tail
    q->head = q->tail;
    // Update tail to head
    q->tail = curr;
}

原本分數測出來 71/100，結果做完 reverse 後，下降到 65/100。原因待查。
8. q_sort:

## TODO
- [ ] Valgrind
- [ ] 論文 Dude, is my code constant time?