# 2018q3 Homework2 (lab0)
###### tags: `System-Software-2018`
contributed by < `DyslexiaS` >

[作業說明](https://hackmd.io/s/BJp_jq-tm)
[C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
>git commit message 應該以動詞開頭，具體寫出做了什麼修改。如 "New Q" 這段訊息應改為 "Implement ..."
>[name=課程助教][color=red]

#### 實驗環境

$ uname -a
Linux dyslexia-E5-473G 4.15.0-34-generic #37-Ubuntu SMP Mon Aug 27 15:21:48 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version 
gcc (Ubuntu 7.3.0-16ubuntu3) 7.3.0

---

:::info
[更換遠端伺服器倉庫網址](https://gist.github.com/fokayx/255b228ded2bca1c4f60)
將 git repository 的 https 改為 ssh，並且設定好 ssh-key，之後 git push 就不需要輸入帳號密碼

:::
## 過程
### queue_t data struct
由於 q_size 和 q_insert_tail 都要求 $O(1)$ 的時間複雜度，因此需要隨時去紀錄 tail 和 size

typedef struct {
    list_ele_t *head;
    list_ele_t *tail;
    size_t q_size;
} queue_t;

### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    if (q == NULL)
        return false;
    list_ele_t *newh;
    /* What should you do if the q is NULL? */
    newh = malloc(sizeof(list_ele_t));
    if (newh == NULL)
        return false;
    /* Don't forget to allocate space for the string and copy it */
    /* What if either call to malloc returns NULL? */
    newh->value = strdup(s);
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    if (q->head == NULL)
        q->tail = newh;
    newh->next = q->head;
    q->head = newh;                                                   
    ++q->q_size;
    return true;
}

### 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 */
    if (q == NULL)
        return false;                                                 
    list_ele_t *newt = malloc(sizeof(list_ele_t));
    if (newt == NULL)
        return false;
    else {
        newt->value = strdup(s);
        newt->next = NULL;
        q->tail->next = newt;
        q->tail = newt;
        ++q->q_size;
        return true;
    }
}

### q_free
- 先把 element 清除乾淨才能 free 掉 queue

void q_free(queue_t *q)
{
    /* How about freeing the list elements and the strings? */
    /* Free queue structure */
    if (q == NULL)
        return;
    while (q->head) {
        list_ele_t *tmp = q->head->next;
        free(q->head);
        q->head = tmp;
    }
    free(q);
}      

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    if (q == NULL || q->head == NULL)
        return false;
    if (sp) {
        strncpy(sp, (q->head)->value, bufsize - 1); 
        *(sp + bufsize - 1) = '\0';
        list_ele_t *tmp = q->head;                                    
        q->head = q->head->next;
        //free(tmp->value);
        free(tmp);
        --q->q_size;
        return true;
    }   
    return false;
}

>**strncpy description**
>Warning: If there is no null byte among the first n bytes of src, the string placed in dest will not be null-terminated.
- 在第 8 行的地方卡了很久，因為在做 strncpy 並沒有複製到 terminating null byte ('\0')，造成字串後面多了很多奇怪的東西，加上 '\0' 就解決了
>**strdup description**
>The strdup() function returns a pointer to a new string which is a duplicate of the string s. Memory for the new string is obtained with malloc(3), and can be freed with free(3).
- 在第 11 行的地方，tmp->value 是由 strdup 在 free 掉 element 之前需要先 free 掉裡面的 value，但執行第 10 行卻會造成錯誤，後來發現有其他同學也遇到相同的狀況。
- harness.h 有段 macro 會把 free 替換成自己的函式，因此我們所用的 free 不是真的 free :confused:
- ## q_reverse

void q_reverse(queue_t *q)
{
    /* You need to write the code for this function */
    if (q == NULL || q->q_size == 0)
        return;
    list_ele_t *tmp = q->head->next;
    q->tail = q->head;
    while (tmp) {
        q->tail->next = tmp->next;
        tmp->next = q->head;
        q->head = tmp;
        tmp = q->tail->next;
    }
}    

- 一開始想要用兩個 tmp 去紀錄當前的 node 以及 下一個 node，後來同學提醒可以用 tail->next 去紀錄，便能省去在創一個暫存的空間了
- 一開始還把 node 數為 1, 2 的狀況獨立出來寫，但後來發現可以全部都使用同一個 while 來解決～
:::info
#### 步驟
> 藍色箭頭為 node 指向位置
> 黑色箭頭才是 node->next
> 紅色箭頭為當次轉向的動作
1. 將 tail 指向 head，所以現在 tail 和 head 都是第 1 個 node
2. 將 tmp 賦值成 head->next (也就是第 2 個 node)
3. 開始做 **while** 迴圈，結束條件為 tmp == NULL，因此當節點只有 1 個時，便不會做以下步驟
4. 將 tmp->next 存起來，才不會讓 a2 指向 a1 後，取不到 a3

5. 將 tmp(a2) 轉向，指到 a1
6. 將 HEAD 和 tmp 往前推進
---
- 重複以上 step4 - step6
- 跳出迴圈時，tmp 是 NULL， tail->next 也剛好是 NULL，因此也省掉手動把 tail->next 變成 NULL (一舉兩得:smile_cat:
- 結束時

:::
## qtest 的行為和技巧
### void *test_malloc(size_t size) `<harness.h>`
在 harness.h 裡有這麼一段 macro：

#define malloc test_malloc

因此我們使用 malloc 時，其實是用了 test_malloc，接著來看看 malloc 實際上會做什麼事情，以下以 doubly-linked list 來對 blocks 進行操作

typedef struct BELE {
    struct BELE *next;
    struct BELE *prev;
    size_t payload_size;
    size_t magic_header; /* Marker to see if block seems legitimate */
    unsigned char payload[0];        
    /* Also place magic number at tail of every block */
} block_ele_t;

節錄 test_malloc：

...
block_ele_t *new_block = malloc(size + sizeof(block_ele_t) + sizeof(size_t));
...
new_block->magic_header = MAGICHEADER;
new_block->payload_size = size;
*find_footer(new_block) = MAGICFOOTER;
void *p = (void *) &new_block->payload;
...

static size_t *find_footer(block_ele_t *b)     
{
    size_t *p = (size_t *) ((size_t) b + b->payload_size + sizeof(block_ele_t));
    return p;
}

當我們 malloc 一個 `list_ele_t` 時，會被夾在 magic_header 和 find_footer 回傳的 footer 中間
其中` unsigned char payload[0]; ` 是一不佔空間的變數（Struct Hack技巧），用來存 `list_ele_t` 的起始位置
> GCC manual 6.17 : [Arrays of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) (Flexible array member)

- 實際 malloc 的大小會是三塊加起來，MAGICHEADER, MAGICFOOTER 就是用來標記`list_ele_t` 邊界的紀錄點，因此在 test_free() 裡，`footer != MAGICFOOTER` 就會有 MSG_ERROR
>Corruption detected in block with address %p when attempting to free it
:::info
#### C99 Flexible array member:
- sizeof( ) 不可使用在incomplete type的變數上
- 只可宣告為一個non-empty structure的最後一個成員

- 因此以下的宣告方式都會造成編譯錯誤：

// Error: flexible array member in otherwise empty struct
struct line {
    char contents[];
};
// Error: flexible array member not at end of struct
struct line {
    char contents[];
    int length;
};

---

struct line {
        int length;
        char contents[];
};
 
struct lines {
        struct line l;
        int line_num;
};

以上 code 會有潛在的 stack smashing detected 問題

[詳見](http://frankchang0125.blogspot.com/2013/01/c-struct-hack-structure-with-variable.html)
:::

## 自動評分系統運作原理
## GitHub