contributed by <Zames-Chang
>
認真看作業要求,除了提及如何逐步達到要求,還需要進行:
還未達成符合預期目標,請繼續付出!
基本上我們要完成這幾個function:
q_insert_tail and q_size 這兩個function必須要是
/*
為了滿足要是o(1),所以必須要在增加tail
讓插入尾巴時不需要從頭路過到尾才能插入,
且增加size屬性,每次insert or remove都紀錄size
*/
typedef struct {
list_ele_t *head;
list_ele_t *tail;
size_t size;
} queue_t;
/*
基本上就是 init queue_t的成員
*/
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
/* What if malloc returned NULL? */
if (!q) {
return NULL;
}
q->size = 0;
q->head = NULL;
q->tail = NULL;
return q;
}
/*
size = strlen(s) + 1 因為有中止符號
然後去 check malloc的過程中有沒有 null的發生,如果都沒有就是把 newh 裡面的資訊填一填,最後再把 q->head指向它就可以了。
最後 size++去 maintain size的資訊
*/
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
size_t size;
if (!q)
return false;
/* 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)
return false;
size = (size_t) strlen(s) + 1;
newh->value = (char *) malloc(size);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
if (!q->head) {
newh->next = NULL;
q->head = newh;
q->tail = newh;
} else {
newh->next = q->head;
q->head = newh;
}
q->size++;
return true;
}
/*
這一個 function是去把這個 element中所有的東西都 free掉不管是它本身有的指標還是指標指到的內容
且把文字給放入 sp這個暫存的 buffer中。
*/
#define min(a, b) (((a) < (b)) ? (a) : (b))
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (!q || !q->head)
return false;
list_ele_t *head = q->head;
if (sp && head->value) {
size_t len = min(strlen(head->value), bufsize - 1);
memcpy(sp, head->value, len);
sp[len] = '\0';
}
q->head = q->head->next;
free(head->value);
free(head);
q->size--;
return true;
}
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 */
list_ele_t *newh;
size_t size;
if (!q)
return false;
newh = malloc(sizeof(list_ele_t));
if (!newh)
return false;
size = (size_t) strlen(s) + 1;
newh->value = (char *) malloc(size);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
newh->next = NULL;
if (!q->head) {
q->head = newh;
q->tail = newh;
} else {
q->tail->next = newh;
q->tail = newh;
}
q->size++;
return true;
}
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) // 如果 q是指到 null 則回傳 0
return 0;
return q->size;
}
void q_free(queue_t *q)
{
/* How about freeing the list elements and the strings? */
/* Free queue structure */
list_ele_t* remove_ele; //暫存準備要移掉的element
if (q) {// 如果有 q存在
if (!q->head){
free(q); // 如果 q是空的
}
else{
while(q->head){
remove_ele = q->head;//先把要移掉的位址暫存起來
q->head = q->head->next; //更新當前的頭指到的地方
free(remove_ele->value); //把字串空間 free掉
free(remove_ele); //把 element本身的空間 free掉
}
free(q);
}
}
}
改寫為下方程式碼: (減少縮排的深度和 scope)
void q_free(queue_t *q)
{
if (!q)
return;
if (!q->head) {
free(q);
return;
}
while (q->head) {
list_ele_t *remove_ele = q->head;
q->head = q->head->next;
free(remove_ele->value);
free(remove_ele);
}
free(q);
}
我之前為了測試環境提交了 commit,被罵惹,然後我用 git rebase試著想去刪掉那個 commit,可是不知道怎弄整個版本都壞掉了,我就整個砍掉重來 ORZ
幻滅是成長的開始,找出因應方法,繼續!
void q_reverse(queue_t *q)
{
if (q && q->head) { // check queue是否為空
list_ele_t *pre = q->head;
list_ele_t *current = q->head->next;
list_ele_t *next;
list_ele_t *temp;
while (current) {
next = current->next; //把當前的下一個點存起來
current->next = pre; // 當前的元素只向上一個元素
pre = current; // 更新上一個元素
current = next; //更新當前元素
}
q->head->next = NULL; // 把原本的 head指向終點 null
//swap tail and head
temp = q->head;
q->head = q->tail;
q->tail = temp;
}
/* You need to write the code for this function */
}
自動化評分時,會下 make test
test: qtest scripts/driver.py
scripts/driver.py
所以看起來他是把 driver.py 餵給了 qtest,那我們先來看看 driver做了什麼
class Tracer:
...
traceProbs = {
1 : "Trace-01",
2 : "Trace-02",
3 : "Trace-03",
4 : "Trace-04",
5 : "Trace-05",
6 : "Trace-06",
7 : "Trace-07",
8 : "Trace-08",
9 : "Trace-09",
10 : "Trace-10",
11 : "Trace-11",
12 : "Trace-12",
13 : "Trace-13",
14 : "Trace-14",
15 : "Trace-15"
}
...
從這段可以猜出他把 trace-01-15代到 qtest裡面跑,再去看
trace-01-ops.cmd
# Test of insert_head and remove_head
option fail 0
option malloc 0
new
ih gerbil
ih bear
ih dolphin
rh dolphin
rh bear
rh gerbil
所以大概就知道每一個 trace檔裡面放的都是 qtest的指令, driver的工作就是把每一個 trace檔都給 qtest跑過。
那來看看 他怎麼 check你有沒有 memory leak,發現他自己 maintain了一個變數叫allocated_count
size_t bcnt = allocation_check();
if (bcnt > 0) {
report(1, "ERROR: Freed queue, but %lu blocks are still allocated",
bcnt);
size_t allocation_check()
{
return allocated_count;
}
然後在哪裡這個變數會增加或減少呢?
這段程式碼取代了原本的malloc 跟free,也就是說每次我們做malloc跟free其實都是call下面兩個程式碼,在這兩段程式碼會有allocated_count++;
and allocated_count--;
,所以他檢查方式就是你allocate幾次空間,就應該要free掉幾次,如果你的最後次數相減不為零代表說你memory leak
...
#define malloc test_malloc
#define free test_free
...
void *test_malloc(size_t size)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to malloc disallowed");
return NULL;
}
if (fail_allocation()) {
report_event(MSG_WARN, "Malloc returning NULL");
return NULL;
}
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;
void *p = (void *) &new_block->payload;
memset(p, FILLCHAR, size);
new_block->next = allocated;
new_block->prev = NULL;
if (allocated)
allocated->prev = new_block;
allocated = new_block;
allocated_count++;
return p;
}
void test_free(void *p)
{
if (noallocate_mode) {
report_event(MSG_FATAL, "Calls to free disallowed");
return;
}
if (p == NULL) {
report(MSG_ERROR, "Attempt to free NULL");
error_occurred = true;
return;
}
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;
memset(p, FILLCHAR, b->payload_size);
/* Unlink from list */
block_ele_t *bn = b->next;
block_ele_t *bp = b->prev;
if (bp)
bp->next = bn;
else
allocated = bn;
if (bn)
bn->prev = bp;
free(b);
allocated_count--;
}
signal(SIGSEGV, sighandler) // if segmentation fault execute sighandler
signal(SIGSLRM, sighandler) // if timeout execute sighandler