# 2019q1 Homework1 (lab0) contributed by < `yunchi0921` > ###### tags: `linux_kernel` --- ## 題目需求 * 實作 queue.c * q_free : 釋放整個queue,包含其string * q_insert_tail : 在尾端插入元素 * q_new : 新建一個queue * q_remove_head : 從開頭端刪除一個元素 * q_reverse : 將queue反轉 * q_size : 計算queue中元素數量 ## 實作 ### `queue_t` 為了讓依題目要求`q_size` & `q_insert_tail`能再O(1)執行而新增一`tail`指標與`qsize`再插入與刪除時隨時紀錄。 ```clike 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 */ list_ele_t *tail; /*In order to let q_insert_tail operate in O(1) */ size_t qsize; } queue_t; ``` ### `q_free` 因為要同時清除 string 與 list element 所以宣告`*cur`與`*prev`，每一次`while`迴圈中,`prev`指向`cur`位置,而`cur`指向下一個位址,由`prev`負責清除,直到`cur`指向`NULL`為止。 ```clike void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ if (q != NULL) { list_ele_t *cur = q->head; list_ele_t *prev = NULL; while (cur) { prev = cur; cur = cur->next; free(prev->value); free(prev); } } free(q); } ``` 這裡藉由同學幫助發現當我`q`為NULL時，沒有返回return，則如果情況發生則會free到一個NULL的位置而產生問題。 修改如下 ```clike void q_free(queue_t *q) { /* How about freeing the list elements and the strings? */ /* Free queue structure */ if (q != NULL) { list_ele_t *cur = q->head; list_ele_t *prev = NULL; while (cur) { prev = cur; cur = cur->next; free(prev->value); free(prev); } }else return; free(q); } ``` ### `q_new` 根據註解判斷queue是否為空,若不是則初始化各值並回傳。 ```clike queue_t *q_new() { queue_t *q = malloc(sizeof(queue_t)); /* What if malloc returned NULL? */ if (q) { q->head = NULL; q->tail = NULL; q->qsize = 0; } else return NULL; return q; } ``` ### `q_insert_head` 這裡值得注意的是tail的連接,實作方式是當queue的size為1時，就將tail指向新element。 ```clike bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; /* What should you do if the q is NULL? */ if (!q) { printf("quene is NULL\n"); return false; } else { 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) { // including null character newh->value = (char *) malloc(strlen(s) + 1); if(newh->value) strcpy(newh->value, s); newh->next = q->head; q->head = newh; (q->qsize)++; /*If only one element in queue , head and tail are on same element. */ if (q->qsize == 1) q->tail = newh; return true; } else { return false; } } } ``` 這邊也有一個問題，如果當`newh->value`配置失敗的時候，我應該`free(newh)`並return `false`，以避免memory leak。 修改如下，同時`q_insert_tail`也相同，不贅述直接修改程式碼。 ```clike bool q_insert_head(queue_t *q, char *s) { list_ele_t *newh; /* What should you do if the q is NULL? */ if (!q) { printf("quene is NULL\n"); return false; } else { 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) { // including null character newh->value = (char *) malloc(strlen(s) + 1); if(newh->value) strcpy(newh->value, s); else{ free(newh); return false; } newh->next = q->head; q->head = newh; (q->qsize)++; /*If only one element in queue , head and tail are on same element. */ if (q->qsize == 1) q->tail = newh; return true; } else { return false; } } } ``` ### `q_insert_tail` 概念基本上跟q_insert_head差不多 ```clike= 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; /*If the q is NULL*/ if (!q) { printf("queue is NULL\n"); return false; } else { newh = malloc(sizeof(list_ele_t)); if (newh) { newh->value = (char *) malloc(strlen(s) + 1); if(newh->value) strcpy(newh->value, s); else{ free(newh); return false; } newh->next = NULL; if (q->tail != NULL) q->tail->next = newh; q->tail = newh; (q->qsize)++; /*If only one element in queue , head and tail are on same element. */ if (q->qsize == 1) { q->head = q->tail; } return true; } else { return false; } } } ``` ### `q_remove_head` 根據註解`sp`不為NULL時要將刪除之 string 複製到`sp`中，且別忘記清除 string 以及 list element。 ```clike bool q_remove_head(queue_t *q, char *sp, size_t bufsize) { /* You need to fix up this code. */ list_ele_t *prev = NULL; if (q->qsize != 0 && q != NULL) { if (sp != NULL) { memset(sp, '\0', bufsize); strncpy(sp, q->head->value, bufsize - 1); } prev = q->head; q->head = q->head->next; /* Free the element and the string */ free(prev->value); free(prev); (q->qsize)--; return true; } else { return false; } } ``` 這邊有一個問題需要注意 ```clike if (q->qsize != 0 && q != NULL) ``` 題目要求說，當queue為空以及q為NULL的時候回傳false，但因為我`q->qsize`寫在前面的關係，compiler在當q為NULL時，會判定我去讀一個NULL pointer，故應該要寫成以下型式 ```clike if (q!= NULL && q->size != 0) ``` ### `q_size` 題目要求在O(1)時間內執行，所以在`queue.h`更改`queue_t`新增`qsize`以達到此目的。 ```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 != NULL) return q->qsize; else return 0; } ``` ### `q_reverse` 這邊我參考[geeksforgeeks](https://www.geeksforgeeks.org/reverse-a-linked-list/)中3個指標的方式，裡頭有一個 gif 檔描述的相當清楚，但與我們不同的是，除了要改變 head ，同時也要改變 tail 。 ```clike void q_reverse(queue_t *q) { /* You need to write the code for this function */ if (q == NULL || q->qsize == 0) return; else { q->tail = q->head; list_ele_t *prev = NULL; list_ele_t *cur = q->head; list_ele_t *next = NULL; while (cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } q->head = prev; } } ``` ## `testmalloc`與`testfree` 感謝[0xff07](https://hackmd.io/s/SJnc7dtSN)詳細的解釋 這邊主要對`find_header` 及`find_free`看看有什麼想講的，以及許多不懂的問題。 ```clike static block_ele_t *find_header(void *p) { if (p == NULL) { report_event(MSG_ERROR, "Attempting to free null block"); error_occurred = true; } block_ele_t *b = (block_ele_t *) ((size_t) p - sizeof(block_ele_t)); if (cautious_mode) { /* Make sure this is really an allocated block */ block_ele_t *ab = allocated; bool found = false; while (ab && !found) { found = ab == b; ab = ab->next; } if (!found) { report_event(MSG_ERROR, "Attempted to free unallocated block. Address = %p", p); error_occurred = true; } } if (b->magic_header != MAGICHEADER) { report_event( MSG_ERROR, "Attempted to free unallocated or corrupted block. Address = %p", p); error_occurred = true; } return b; } ``` 首先`find_header`主要是藉由`block_ele_t`的大小來推算出header在哪邊，接下來則是一連串的檢查機制。 ```clike block_ele_t *ab = allocated; bool found = false; while (ab && !found) { found = ab == b; ab = ab->next; } if (!found) { report_event(MSG_ERROR, "Attempted to free unallocated block. Address = %p", p); error_occurred = true; } ``` 這邊`ab`指向`allocated`這個doubly-linked list的開頭，並且在迴圈中搜尋這個block到底有沒有再這個串列裡頭 ```clike if (b->magic_header != MAGICHEADER) { report_event( MSG_ERROR, "Attempted to free unallocated or corrupted block. Address = %p", p); error_occurred = true; } ``` 這段程式我則不太明白，因為在`test_malloc`當中每個new_block的`magic_header`都會被指定成`MAGICHEADER`，這樣子與上一段的檢查，發現他已經是allocated的一個block，這樣子 `b->magic_header`一定會在`test_malloc`被指定為`MAGICHEADER`才對，有種重複檢查沒有必要感覺。 ```clike new_block->magic_header =MAGICHEADER; ``` 我猜應該是因為 `cautious mode` 關閉的時候而存在的機制，不曉得正不正確。