###### tags: `linux2019`
# 2019q1 Homework1 (lab0)
contributed by < `ambersun1234` >
## 環境
```shell
$ uname -a
Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.11)
```
## 說明
+ [作業說明](https://hackmd.io/s/BJA8EgFB4)
+ [C Programming Lab](http://www.cs.cmu.edu/~213/labs/cprogramminglab.pdf)
## 題目摘要
+ 實做一個可以支援 FIFO , LIFO 的 queue
+ 在 queue.h & queue.c 中修改以下 function
+ q_new: 新增一個空的 queue
+ q_free: 釋出所有被 queue 使用的資源
+ q_insert_head: 在 queue 的最前方新增一個新的資料( LIFO )
+ q_insert_tail: 在 queue 的最後方新增一個新的資料( FIFO )
+ q_remove_head: 移除最前方的資料
+ q_size: 取得目前 queue 的資料數量
+ q_reverse: 反轉 queue( 此 function 不應該新增或刪除任何 queue 裡面的資料 )
## 實驗紀錄
+ q_new
```c=1
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (q == NULL) {
return NULL;
} else {
q->head = NULL;
q->q_size = 0;
q->last = q->head;
return q;
}
}
```
+ malloc 之後必須要確定是否成功，所以要檢查回傳值是否為 NULL
+ q_free
```c=1
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
if (q != NULL) {
list_ele_t *current = q->head, *next;
while (current != NULL) {
next = current->next;
free(current->value);
free(current);
current = next;
}
free(q);
}
}
```
+ q_insert_head
```c=1
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));
/* Don't forget to allocate space for the string and copy it */
/* What if either call to malloc returns NULL? */
if (newh == NULL) {
return false;
} else {
newh->value = strdup(s);
if (newh->value == NULL) {
free(newh);
return false;
}
newh->next = q->head; // newh->next will definitely be head
if (q->head == NULL) {
// queue empty
q->last = newh;
}
q->head = newh;
q->q_size++;
return true;
}
}
```
+ newh->value 我原本是用 malloc 的方式實做，但是在後來的 free 以及 quit 中都寫到說類似 `ERROR: Freed queue, but 4 blocks are still allocated` 的東西。因此我參考了 [DyslexiaS 的開發紀錄](https://hackmd.io/s/Byjnik5F7)，將 malloc 替換成 strdup 的方式實做才解決了問題
+ 還有就是在將新的節點插入進 queue 的時候我使用了較多的 if else 判斷導致程式碼過於冗長，[DyslexiaS 的開發紀錄](https://hackmd.io/s/Byjnik5F7) 也提供給我了一個另一種的解法，即將 newh->next 指向 q->head ( 因為 newh 必定會成為 queue 的第一個 )
+ q_insert_tail:
```c=1
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; /* Current linked list size */
list_ele_t *last; /* Store last node */
} queue_t;
```
+ `q_insert_tail` 要求 $O(1)$，因此在 `queue_t` 中新增了 `list_ele_t *last` 用以紀錄當前 queue 中最後一個元素
```c=1
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 *newh;
newh = malloc(sizeof(list_ele_t));
if (newh == NULL) {
return false;
} else {
newh->value = strdup(s);
if (newh->value == NULL) {
free(newh);
return false;
}
newh->next = NULL;
if (q->last == NULL) {
q->head = q->last = newh;
} else {
q->last->next = newh;
q->last = newh;
}
q->q_size++;
return true;
}
}
```
+ q_remove_head:
```c=1
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;
} else {
if (sp != NULL) {
strncpy(sp, q->head->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_ele_t *temp = q->head;
q->head = q->head->next;
q->q_size--;
free(temp->value);
free(temp);
return true;
}
}
```
+ q_size:
```c=1
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; /* Current linked list size */
list_ele_t *last; /* Store last node */
} queue_t;
```
+ 為了達到 $O(1)$，我在 queue_t 中新增了 `int q_size` 紀錄了當前 queue 的 element 數量
```c=1
int q_size(queue_t *q)
{
/* You need to write the code for this function */
/* Remember: It should operate in O(1) time */
return q->q_size;
}
```
+ q_reverse:
```c=1
void q_reverse(queue_t *q)
{
/* You need to write the code for this function */
if (q == NULL) {
return;
}
list_ele_t *previous = NULL, *current = q->head, *next = q->head;
q->last = q->head;
while (next != NULL) {
// store
next = current->next;
// reverse
current->next = previous;
// move on
previous = current;
current = next;
}
q->head = previous;
}
```
## 自動評分系統運作的原理
+ 根據 Makefile 的內容可以得知，自動評分系統是使用了 python 來進行評分的
+ 最主要評分的 function 是 `Tracer` 裡面的 `run` & `runTrace`，評分的項目總共有15個，定義於 `Tracer` 裡面的 `traceDict` ; 其個別對應到的是 ./traces 的15個指令檔案
+ 在 `run` 中是先做一些初始化設定，然後接著用一個 for 迴圈跑 `traceDict` 的 keys，之後在呼叫 `runTrace`
```python=1
def run(self, tid = 0):
scoreDict = { k : 0 for k in self.traceDict.keys() }
print("---\tTrace\t\tPoints")
if tid == 0:
tidList = self.traceDict.keys()
else:
if not tid in self.traceDict:
print("ERROR: Invalid trace ID %d" % tid)
return
tidList = [tid]
score = 0
maxscore = 0
if self.useValgrind:
self.command = 'valgrind'
else:
self.command = self.qtest
self.qtest = ''
for t in tidList:
tname = self.traceDict[t]
if self.verbLevel > 0:
print("+++ TESTING trace %s:" % tname)
ok = self.runTrace(t)
maxval = self.maxScores[t]
tval = maxval if ok else 0
print("---\t%s\t%d/%d" % (tname, tval, maxval))
score += tval
maxscore += maxval
scoreDict[t] = tval
print("---\tTOTAL\t\t%d/%d" % (score, maxscore))
if self.autograde:
# Generate JSON string
jstring = '{"scores": {'
first = True
for k in scoreDict.keys():
if not first:
jstring += ', '
first = False
jstring += '"%s" : %d' % (self.traceProbs[k], scoreDict[k])
jstring += '}}'
print(jstring)
```
+ `runTrace` 中使用了 `subprocess.call` 呼叫子行程用以執行各個 `traceDict` 的檔案，若子行程執行中出錯，則 retcode 就不是0
```python=1
def runTrace(self, tid):
if not tid in self.traceDict:
print("ERROR: No trace with id %d" % tid)
return False
fname = "%s/%s.cmd" % (self.traceDirectory, self.traceDict[tid])
vname = "%d" % self.verbLevel
clist = [self.command, self.qtest, "-v", vname, "-f", fname]
try:
retcode = subprocess.call(clist)
except Exception as e:
print("Call of '%s' failed: %s" % (" ".join(clist), e))
return False
return retcode == 0
```
+ 最後評分是依據 `runTrace` 的回傳值來判斷要給幾分
```python=1
tval = maxval if ok else 0
```
maxval 是各個項目的最高分 ( t 為當前 traceDict 的 key )
```python=1
maxval = self.maxScores[t]
```
## qtest的行為和技巧
+ qtest 實際上是透過一層包裝來呼叫 function( q_insert_head , q_insert_tail , q_reverse ... etc. )，這些所謂的包裝是定義在 qtest.c裡面，如下所示
```c=1
bool do_new(int argc, char *argv[]);
bool do_free(int argc, char *argv[]);
bool do_insert_head(int argc, char *argv[]);
bool do_insert_tail(int argc, char *argv[]);
bool do_remove_head(int argc, char *argv[]);
bool do_remove_head_quiet(int argc, char *argv[]);
bool do_reverse(int argc, char *argv[]);
bool do_size(int argc, char *argv[]);
bool do_show(int argc, char *argv[]);
```
+ 而以上的這些 function 是以 function pointer 的形式透過 `add_cmd()` 儲存到 `單向` linked list 裡面，linked list 的設計是為了方便使用者自行增加 function 到互動界面上
+ 值得注意的是，在 `harness.h` 中有寫到
```c=1
#define malloc test_malloc
#define free test_free
#define strdup test_strdup
```
+ 意思就是說，該程式將這些 function 改成自己的版本，這個大概也就可以解釋為什麼我嘗試要 malloc newh->value 的時候會有錯誤
+ 更深入的閱讀程式碼之後我發現到，`test_malloc` 實際上是用一個更大的空間來儲存記憶體相關的東西，而且是使用 `雙向 linked list` 儲存
+ 以下這個 struct 是用來儲存記憶體相關的東西
```c=1
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));`
可以發現到除了 block_ele_t 之外還有 size 跟 sizeof(size_t)，其中 size 就是在 malloc 時的參數，另外一個是跟所謂的 `magic number` 有相關
> magic number: 程式設計中將一個數字寫死，用以表達特殊意義
+ 在 block_ele_t 中 magic_header 用以儲存此 struct 的記憶體狀態，回到真正 malloc 的地方，最後一個 `sizeof(size_t)` 即是要儲存 magic_footer 的
```c=1
/* Value at start of every allocated block */
#define MAGICHEADER 0xdeadbeef
/* Value when deallocate block */
#define MAGICFREE 0xffffffff
/* Value at end of every block */
#define MAGICFOOTER 0xbeefdead
```
+ `test_malloc` 的回傳值是定義成
`void *p = (void *) &new_block->payload;`
剛開始我很不明白為什麼是 payload ，而且他的大小還是0，後來有查到一個叫做 <font color=red>struct hack</font> 的東西
+ cf. `struct hack`
+ 使用這個方法可以使 struct 達到動態記憶體分配
+ 在 struct 的最後新增一個大小為0的陣列
+ 然後在 malloc 的時候要求空間除了原本 struct 之外再加上額外需求空間
> [reference struct hack](http://frankchang0125.blogspot.com/2013/01/c-struct-hack-structure-with-variable.html)
+ 以 struct hack 的方法即可以分配記憶體給 list_ele_t
+ 其中還有 `static size_t allocated_count = 0;` 用以紀錄目前 allocated 的記憶體數量
Sign in with Wallet
Connect another wallet