# 2023 lab-0 ## q_new ```c struct list_head *q_new() { struct list_head *head = malloc(sizeof(*head)); if (!head) return NULL; INIT_LIST_HEAD(head); return head; } ``` ## q_size des: ```c int q_size(struct list_head *head) { if (!head) return 0; int len = 0; struct list_head *li; list_for_each (li, head) len++; return len; } ``` ## q_insert_head and q_insert_tail ```c= bool q_insert_head(struct list_head *head, char *s) { if (!head) return false; element_t *node = malloc(sizeof(element_t)); if (!node) return false; size_t s_len = strlen(s) + 1; node->value = malloc(s_len * sizeof(char)); if (!node->value) return false; memcpy(node->value, s, s_len); list_add(&node->list, head); return true; } ``` 兩者的實作方式基本上大同小異，差別只在於13行`q_insert_tail`裡使用的是`list_add_tail`但是在commit時噴: ```bash $ git commit Following files need to be cleaned up: queue.c queue.c:38:9: error: Memory leak: node [memleak] return false; ^ queue.c:55:9: error: Memory leak: node [memleak] return false; ^ Fail to pass static analysis. ``` 參考: https://hackmd.io/@25077667/lab0-2023 寫法 若malloc(7.22.3.1)失敗還是需要使用free釋放 對於`free`的描述(7.22.3.3): >If ptr is a null pointer, no action occurs. [c stard](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf) 經過查證: double free 產生的條件在記憶體釋放之後又重複做了一次釋放，要避免這一情況，可以在釋放之後將記憶體的指標位置設置為NULL example: ```c #include<stdio.h> int main() { char *myptr = malloc(sizeof(char)); free(myptr); free(myptr); return 0; } ``` 避免產生double的情況: ```c #include<stdio.h> int main() { char *myptr = malloc(sizeof(char)); free(myptr); myptr = NULL; free(myptr); return 0; } ``` [reference](https://blog.gtwang.org/programming/memory-deallocation-issues-in-c/) ## q_free ```c void q_free(struct list_head *l) { if(!l) return; element_t *node, *safe; list_for_each_safe(node, safe, l) { q_release_element(list_entry(node, element_t, list)); } } ``` 原本實作的方式為以上，但在使用`make check`後噴錯: ```bash= ERROR: There is no queue, but 1 blocks are still allocated # Exit program Freeing queue ERROR: Freed queue, but 1 blocks are still allocated make: *** [Makefile:57: check] Error 1 ``` 顯示有記憶體沒有被釋放掉。 - 分析: list_for_each_safe 定義: ```c #define list_for_each_safe(node, safe, head) \ for (node = (head)->next, safe = node->next; node != (head); \ node = safe, safe = node->next) ``` 以我帶入的參數:`list_for_each_safe(node, safe, l)` 展開得到以下: `for (node = (l)->next, safe = node->next; node != (l); node = safe, safe = node->next)` 結果顯示l指標本身的指標並未被釋放掉，因此修改程式碼為: ```c void q_free(struct list_head *l) { if(!l) return; struct list_head *node, *safe; list_for_each_safe(node, safe, l) { q_release_element(list_entry(node, element_t, list)); } free(l); } ``` ## q_remove_tail &q_remove_head des:移除queue的頭&尾部的element_t ，並將該element_t回傳 parameter: algorithm:使用list_first_entry & list_last_entry 取得頭或尾的element指標，將element_t中的string設定到參數sp中 ```c element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; element_t *obj = list_first_entry(head, element_t, list); size_t len = strlen(obj->value); if (len > bufsize) len = bufsize; memcpy(sp, obj->value, len); list_del(&obj->list); return obj; } element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize) { if (!head) return NULL; element_t *obj = list_last_entry(head, element_t, list); size_t len = strlen(obj->value); if (len > bufsize) len = bufsize; memcpy(sp, obj->value, len); list_del(&obj->list); return obj; } ``` ## q_reverse des:反轉整個queue的順序 algorithm:使用list_for_safe走遍整個queue並且交換next與prev的值 implement: ```c void q_reverse(struct list_head *head) { struct list_head *safe; struct list_head *node; list_for_each_safe(node, safe, head) { struct list_head *tmp = node->next; node->next = node->prev; node->prev = tmp; } } ``` ## q_delete_mid des:刪除串列中間的節點，n個節點則刪除n/2+1 eg.有三個節點則刪除第1個(最前面的節點為第0個)，如果有四個節點則刪除第2個節點 algorithm:使用快慢指標 implement: ```c bool q_delete_mid(struct list_head *head) { // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/ if (!head || list_empty(head)) return false; struct list_head **slow = &head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) { slow = &(*slow)->next; } list_del(*slow); q_release_element(list_entry(*slow, element_t, list);); return true; } ``` 原本使用指向指標的指標來實作，直到跑test的時候才發現問題，錯誤訊息為:`Segmentation fault occurred. You dereferenced a NULL or invalid pointer`看了一下程式碼，表面上看起來演算法沒有什麼太大的問題，為了debug使用了printf分別印出幾個變數值之後才發現問題，首先修改程式碼如下: ```c= bool q_delete_mid(struct list_head *head) { if (!head || list_empty(head)) return false; struct list_head **slow = &head->next; for (struct list_head *fast = head->next; fast != head && fast->next != head; fast = fast->next->next) { slow = &(*slow)->next; } struct list_head *tmp = *slow; printf("tmp 1 is %p\n",tmp); printf("&tmp->prev->next 1 is %p\n",&tmp->prev->next); printf("tmp->next 1 is %p\n",tmp->next); printf("slow 1 is %p\n",slow); printf("*slow 1 is %p\n",*slow); list_del(tmp); printf("tmp is %p\n",tmp); printf("&tmp->prev->next is %p\n",&tmp->prev->next); printf("tmp->next is %p\n",tmp->next); printf("slow is %p\n",slow); printf("*slow is %p\n",*slow); element_t *tmpobj = list_entry(*slow, element_t, list); q_release_element(tmpobj); return true; } ``` 結果如下: ```bash= tmp 1 is 0x7fffb9ef20f8 &tmp->prev->next 1 is 0x7fffb9ef19b0 tmp->next 1 is 0x7fffb9ef2188 slow 1 is 0x7fffb9ef19b0 *slow 1 is 0x7fffb9ef20f8 tmp is 0x7fffb9ef20f8 &tmp->prev->next is 0x7fffb9ef19b0 tmp->next is 0x7fffb9ef2188 slow is 0x7fffb9ef19b0 *slow is 0x7fffb9ef2188 ``` 首先使用了一個tmp指標存下前面運算得到的*slow指標，然後在使用list_del的前後分別印出幾個比較關鍵的數值 - 結論:slow由於是一個指標的指標指向的該記憶體位置裡面存放的記憶體因為list_del而被修改 - 原因:slow並不是直接指向那個需要被刪除的節點(之後稱這個節點為target節點)而是指向指向target節點的指標(也就是target前一個節點的next)在使用list_del之前存放的是target節點的位址，使用了list_del之後由於會更改到target節點前一個節點的next值(該值被指向target節點的下一個節點位址)，因此在下一行執行`q_release_element`時會產生錯誤。