# 2019q1 Homework1 (lab0)
contributed by < `njjack` >

:::danger
注意看 [2019q1 Homework1 (作業區)](https://hackmd.io/s/SJ4kPZYS4) 的要求，HackMD 網址應採 publish 後的網址，請留意細節，及早變更。包含空白和排版，均有指定格式。
無論標題和內文中，==中文和英文字元之間要有空白字元== (對排版和文字搜尋有利)
:notes: jserv
:::

[C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 環境
~~~
$ cat /etc/os-release
NAME="Ubuntu"
VERSION="16.04.3 LTS (Xenial Xerus)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 16.04.3 LTS"
VERSION_ID="16.04"
HOME_URL="http://www.ubuntu.com/"
SUPPORT_URL="http://help.ubuntu.com/"
BUG_REPORT_URL="http://bugs.launchpad.net/ubuntu/"
VERSION_CODENAME=xenial
UBUNTU_CODENAME=xenial
~~~
~~~
$ lscpu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 61
Model name: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
製程： 4
CPU MHz： 1609.716
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
BogoMIPS: 4389.82
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3

~~~

## 題目

實作 queue functions
* q_new
* q_free
* q_insert_head
* q_insert_tail
* q_remove_head
* q_size
* q_reverse
## 實作
考慮題目要求 q_insert_tail( ) 和 q_size( ) 執行時間需為 $O(1)$，在 queue_t 結構中加入 `size` 和 `tail`

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

### 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->size = 0;
    return q;
}

### q_free

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

### q_insert_head

bool q_insert_head(queue_t *q, char *s)
{
    /* What should you do if the q is NULL? */
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        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) {
        free(newh);
        return false;
    }

    newh->next = q->head;
    q->head = newh;
    if (q->size == 0) {
        q->tail = newh;
    }
    q->size++;
    return true;
}

### q_insert_tail

bool q_insert_tail(queue_t *q, char *s)
{
    if (!q) {
        return false;
    }
    list_ele_t *newh;
    newh = malloc(sizeof(list_ele_t));
    if (!newh) {
        return false;
    }

    newh->value = strdup(s);
    if (!newh->value) {
        free(newh);
        return false;
    }

    newh->next = NULL;
    if (q->size == 0) {
        q->head = newh;
    } else {
        q->tail->next = newh;
    }
    q->tail = newh;
    q->size++;
    return true;
}

### q_remove_head

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (q == NULL || q->size == 0) {
        return false;
    }
    list_ele_t *temp = q->head;
    if (sp) {
        memcpy(sp, temp->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    q->head = temp->next;
    free(temp);
    q->size--;
    return true;
}

### q_size

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)
        return 0;
    return q->size;
}

### q_reverse

void q_reverse(queue_t *q)
{
    if (q == NULL || q->size == 0) {
        return;
    }
    list_ele_t *current = q->head;
    list_ele_t *cnext = current->next;
    list_ele_t *temp = current;
    while (cnext) {
        current = cnext;
        cnext = cnext->next;
        current->next = temp;
        temp = current;
    }
    q->tail = q->head;
    q->tail->next = NULL;
    q->head = current;
}

## 自動評分系統運作原理
### command
command 以 `struct CELE` 表示，儲存在 single linked list 中

struct CELE {
    char *name;
    cmd_function operation;
    char *documentation;
    cmd_ptr next;
};

呼叫 add_cmd 將一個新的 command 加入 linked list 中適當位置（按字母順序排序）

void add_cmd(char *name, cmd_function operation, char *documentation)
{
    cmd_ptr next_cmd = cmd_list;
    cmd_ptr *last_loc = &cmd_list;
    while (next_cmd && strcmp(name, next_cmd->name) > 0) {
        last_loc = &next_cmd->next;
        next_cmd = next_cmd->next;
    }
    cmd_ptr ele = (cmd_ptr) malloc_or_fail(sizeof(cmd_ele), "add_cmd");
    ele->name = name;
    ele->operation = operation;
    ele->documentation = documentation;
    ele->next = next_cmd;
    *last_loc = ele;
}

每次 command 輸入會呼叫 `interpret_cmda` 來搜尋 linked list ，找到並呼叫 command 對應之處理函式
(實際上每次 command 輸入按 function call 順序會呼叫 `cmd_select` , `interpret_cmd` , `parse_args`, 最後才將 parsing 後得到之 "command that has already been split into arguments" 作為 input 呼叫 `interpret_cmda` )

/* Execute a command that has already been split into arguments */
static bool interpret_cmda(int argc, char *argv[])
{
    if (argc == 0)
        return true;
    /* Try to find matching command */
    cmd_ptr next_cmd = cmd_list;
    bool ok = true;
    while (next_cmd && strcmp(argv[0], next_cmd->name) != 0)
        next_cmd = next_cmd->next;
    if (next_cmd) {
        ok = next_cmd->operation(argc, argv);
        if (!ok)
            record_error();
    } else {
        report(1, "Unknown command '%s'", argv[0]);
        record_error();
        ok = false;
    }
    return ok;
}

### memory management
* harness.h 中藉由 macro 將 `malloc` 和 `free` 替換成 `test_malloc` 和 `test_free`

#define malloc test_malloc
#define free test_free

* 以 `block_ele_t` 結構實作一 doubly linked list ，記錄已分配之記憶體空間。
* 其中 `payload[0]` 為 [Array of Length Zero](https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html) 技巧之使用。每一段已分配記憶體空間都有一 `block_ele_t` 結構之 header ，藉由存取 payload 可直接存取此 header 之後的記憶體空間。

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` 實際會分配的記憶體空間，除了提出請求之記憶體大小，還包含 header(一個 `block_ele_t` 結構) 和 tail (一個 magic number)
* `test_malloc` 成功配置記憶體空間後，會將 header 中 `magic_header` 設 `MAGICHEADER` ， 並呼叫 `find_footer` 找到 tail 的 magic number 設為 `MAGICFOOTER`
* `MAGICHEADER` 和 `MAGICFOOTER` 分別為常數 `0xdeadbeef` 和 `0xbeefdead` ，作為存取位置是否合法的判斷依據

void *test_malloc(size_t size)
{
    ...
    block_ele_t *new_block =
        malloc(size + sizeof(block_ele_t) + sizeof(size_t));
    if (new_block == NULL) {
        report_event(MSG_FATAL, "Couldn't allocate any more memory");
        error_occurred = true;
    }
    new_block->magic_header = MAGICHEADER;
    new_block->payload_size = size;
    *find_footer(new_block) = MAGICFOOTER;
    ...
}

* `test_free` 會檢查 tail 的 magic number 是否為 `MAGICFOOTER` ，若否，則釋放此空間非合法動作
* `test_free` 將`magic_header` 和 tail 的 magic number 都設為 `MAGICFREE`

void test_free(void *p)
{
    ...
    block_ele_t *b = find_header(p);
    size_t footer = *find_footer(b);
    if (footer != MAGICFOOTER) {
        report_event(MSG_ERROR,
                     "Corruption detected in block with address %p when "
                     "attempting to free it",
                     p);
        error_occurred = true;
    }
    b->magic_header = MAGICFREE;
    *find_footer(b) = MAGICFREE;
    ...
}

* `test_malloc` 和 `test_free` 都會將配置或是放的記憶體空間初始為常數 `FILLCHAR` 已避免若某位置存放數值恰為前述已使用過之常數，可能造成判斷合法與否時誤判
`