contributed by < yiwei01
>
sysprog2019
To meet the requirement that q_insert_tail
and q_size
operate in time O(1), I add list_ele_t *tail and int size fields in queue_t structure in queue.h.
Allocate memory to new queue. If malloc
dose not return NULL, then initialize the queue and return its starting address, else return NULL.
By adding int size field in queue_t structure, q_size
can operate in time O(1).
Problems encountered and solved :
I forget to check NULL pointer which result in NULL pointer dereference. Hence, I add a NULL pointer check when returning the value.
Before inserting new element, check if queue exists and can allocate enough space. In addition, I use additional variable unsigned int len_s to record the length of s in case that s is NULL but be taken as input of strlen
. When copying string, I use strncpy
and assign '\0' to the last address of (newh->value). At the end, update q->head and q->size (and q->tail if needed).
Problems encountered and solved :
I misusestrcat(newh->value,"\0")
to add terminating character afterstrncpy(newh->value, s, len_s);
. However,strcat
overwrites the terminating null byte ('\0') at the end of dest, so if there is not terminating character in dest, it may has unexpected garbled message in it.
Almost as same as q_insert_head
, the subtle difference is that q_insert_tail
has to check if q->tail exists. If q->tail exists, assign new list element to q->tail->next. At the end, update q->tail and q->size (and q->head if needed).
First, check if there are elements in q can be removed. Second, copying string from q->head->value to sp. Third, use additional variable list_ele_t *tmp to record q->head then remove tmp->value and tmp. At the end, update q->size.
After applying cppcheck, I'm reminded that "Unsigned variable 'bufsize' can't be negative so it is unnecessary to test it." So, I remove unnecessary assertion in Line 3.
Use list_ele_t *ptr to record current q->head and an additional variable list_ele_t *tmp to record ptr->next, after ptr->value and ptr are freed, assign tmp to ptr before go on next iteration. At the end, free q.
If queue is not NULL, use list_ele_t *prev to record the previous list elment and list_ele_t *next to record the next element. Then reverse links by assigning prev to curr->next.
Problem encountered ( Installation ) :
$ cat /proc/sys/kernel/perf_event_paranoid
return 3
solved by :
$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"
or
透過 perf ,我發現我的 q_reverse
算是整支程式的 bottleneck
Todo : 想改進方式
0xff07 同學的筆記已紀錄的很完整,自己理解過後再整理一次重點:
資料結構圖示:
allocated
(doubly linked list) 的下一個 nodeallocated
(doubly linked list) 的上一個 nodemalloc
時要求的大小test_malloc
中便利用了此特性。test_malloc
中初始 magic_header 的值為 0xdeadbeef , magic_footer 的值為 0xbeefdead,因此若該 block 的 magic_header 或 magic_footer 的值被更改,則代表此塊 block 曾被非法存取。回傳 header 與 footer 的位址,其中 find_header
會檢查傳入的 block 是否真的是 allocated block,並檢查 magic_header 是否被更改過
檢查現在是否為可分配的模式、此次分配是否成功、是否擁有足夠空間滿足使用者的要求,若成功則分配空間給使用者,並會在 block 紀錄分配多大的大小、初始 magic_header 與 magic_footer,最後加入 allocated 這個 doubly linked list
檢查現在是否為可分配的模式、欲 free 的空間是否為 NULL、magic_footer 是否被更改過,若通過上述檢查,則將 payload 以 FILLCHAR 來覆蓋,並將 magic_header、 magic_footer assign 為 MAGICFREE,最後移出 doubly linked list
將 strdup
會呼叫到的 malloc
替換為呼叫 test_malloc
.