# 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`
```clike=
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
int size;
} queue_t;
```
### 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->size = 0;
return q;
}
```
### q_free
```clike=
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
```clike=
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
```clike=
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
```clike=
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
```clike=
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
```clike=
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 中
```clike=
struct CELE {
char *name;
cmd_function operation;
char *documentation;
cmd_ptr next;
};
```
呼叫 add_cmd 將一個新的 command 加入 linked list 中適當位置（按字母順序排序）
```clike=
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` )
```clike=
/* 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`
```clike=
#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 之後的記憶體空間。
```clike=
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` ，作為存取位置是否合法的判斷依據
```clike=
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`
```clike=
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` 已避免若某位置存放數值恰為前述已使用過之常數，可能造成判斷合法與否時誤判
`
Sign in with Wallet
Connect another wallet